杭电HDU 3974Assign the task dfs出父包子的数组-＞知道管辖范围，线段树

题目链接：Problem - 3974 (hdu.edu.cn)

别的题解那对数的输入有点复杂，而且不用。。

本题不讲线段树原理，会线段树后来看即可。

思路：

我们建好树，对树dfs。

就题目样例吧：（建树网站：CS Academy）

每个节点进的时候记录，出的时候也记录，dfs完是这个效果

   节点  //2344113552
   下标  //12345678910

比如start数组记录该点左下标 start[2] = 1

       end数组记录右下标 end[2] = 10

所以2管辖的就是1~10，当我们修改2的时候，可以知道范围，对这个段赋值即可

（我练习也比较少，是把区间加线段树改成这个区间赋值的）

代码：

板子就是我博客线段树1改过来的。

第一遍没过，慌得要死，跑了一遍发现我当时线段树只有叶子初始值是-1，改了就过了，嘿嘿。

getsum就是取值，没有改名字。

#define ll long long
template<class T>
class ST//segment tree
{
	struct node
	{
		T val;
		T t;//懒标记//服务后代
		node(T v = 0) :val(v), t(0)
		{}
	};
	ll n = a.size();
	vector<T>a;
	vector<node>d;
public:
	void build_tree(ll i, ll l, ll r)
	{
		d[i].val = -1;
		if (l == r)
		{
			return;
		}
		ll mid = l + (r - l) / 2;
		build_tree(i * 2, l, mid);
		build_tree(i * 2 + 1, mid + 1, r);
		//d[i].val = d[i * 2].val + d[i * 2 + 1].val;
	}
	void spread(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		ll mid = l + (r - l) / 2;
		if (d[i].t != 0 && l != r)
		{
			d[i * 2].val = d[i].t;
			d[i * 2 + 1].val = d[i].t;

			d[i * 2].t = d[i].t;//可能上上次也没改
			d[i * 2 + 1].t = d[i].t;
			d[i].t = 0;
		}
	}
	T getsum(ll l, ll r)
	{
		return _getsum(1, 1, n, l, r);
	}
	T _getsum(ll i, ll l, ll r, ll aiml, ll aimr)
	{
		if (aiml <= l && r <= aimr)//查询区间的子集全部加起来
			return d[i].val;

		//访问
		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);

		if (aiml <= mid)
			return _getsum(i * 2, l, mid, aiml, aimr);
		if (aimr >= mid + 1)
			return _getsum(i * 2 + 1, mid + 1, r, aiml, aimr);
	}
	void update(ll l, ll r, ll val)
	{
		_update(1, 1, n, l, r, val);//加并挂标记
	}
	void _update(ll i, ll l, ll r, ll aiml, ll aimr, ll val)
	{
		if (aiml <= l && r <= aimr)
		{
			d[i].val = val;
			d[i].t = val;
			return;
		}


		ll mid = l + (r - l) / 2;
		spread(i, l, r, aiml, aimr);

		if (aiml <= mid)
			_update(i * 2, l, mid, aiml, aimr, val);
		if (aimr >= mid + 1)
			_update(i * 2 + 1, mid + 1, r, aiml, aimr, val);
	}
	ST(vector<T>arr)
	{
		a = arr;
		n = a.size() - 1;
		d = vector<node>(pow(2, (ll)log2(n) + 1 + 1) - 1 + 1);
		build_tree(1, 1, n);
	}
};
int index;
void dfs(int cur, vector<int>& start, vector<int>& end, vector<vector<int>>& alist)
{
	start[cur] = index++;
	for (int i=0;i<alist[cur].size();i++)
	{
		dfs(alist[cur][i],start,end,alist);
	}
	end[cur] = index++;
}
void solve(int casen)
{
	int n;
	cin >> n;
	vector<vector<int>>alist(n+1);
	vector<int>parent(n+1);
	for (int i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		alist[v].push_back(u);//我的下属
		parent[u] = v;
	}
	int root = 0;
	for (int i = 1; i <= n; i++)
	{
		if (parent[i] == 0)
		{
			root = i;
			break;
		}
	}
	index = 1;
	vector<int>start(n + 1);
	vector<int>end(n + 1);
	dfs(root, start, end, alist);
	//2344113552
	//12345678910
	vector<int>arr(1 + 2 * n,-1);
	ST<ll>demo(arr);

	int m;
	cin >> m;
	cout << "Case #" << casen << ":" << endl;
	for (int i = 1; i <= m; i++)
	{
		char op;
		cin >> op;
		int x, y;
		if (op == 'C')
		{
			cin >> x;
			cout << demo.getsum(start[x], end[x]) << endl;
		}
		else if (op == 'T')
		{
			cin >> x >> y;
			demo.update(start[x], end[x], y);
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	for(int i=1;i<=t;i++)
	{
		solve(i);
	}
	return 0;
}