bzoj传送门

十天时间学了树剖（= =）

这是道裸题，只要单点修改，区间查询。

深搜如下

void FHE(int x,int father,int depth)
{
	fa[x] = father;dep[x] = depth;
	size[x] = 1;
	int maxsize = 0;
	son[x] = 0;
	for (int i = head[x];i;i = last[i])
		if (!visit[h[i]])
		{
			visit[h[i]] = 1;
			FHE(h[i],x,depth+1);
			size[x] += size[h[i]];
			if (size[h[i]] > maxsize)
			{
				maxsize = size[h[i]];
				son[x] = h[i];
			}
		}
}
void CHE(int x,int ancestor)
{
	tid[x] = ++label;
	optid[label] = x;
	top[x] = ancestor;
	if (son[x]) {visit[son[x]] = 1;CHE(son[x],ancestor);}
	for (int i = head[x];i;i = last[i])
		if (!visit[h[i]])
		{
			visit[h[i]] = 1;
			CHE(h[i],h[i]);
		}
}

查询如下

int Respond_max(int x,int y)
{
	int ans = -100000000;
	for (;top[x]-top[y];)
	{
		if (dep[top[x]] < dep[top[y]]) swap(x,y);
		ans = max(ans,tree.query_max(1,tid[top[x]],tid[x]));//tree.query_max就是数据结构的最值查询
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x,y);
	return max(ans,tree.query_max(1,tid[x],tid[y]));
}
int Respond_num(int x,int y)
{
	int ans = 0;
	for (;top[x]-top[y];)
	{
		if (dep[top[x]] < dep[top[y]]) swap(x,y);
		ans += tree.query_num(1,tid[top[x]],tid[x]);//tree.query_num就是数据结构的和查询

		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x,y);
	return ans+tree.query_num(1,tid[x],tid[y]);
}