「NOIP2016」天天爱跑步

题意：

根据题意，可以把任意 $S_i$ 到 $T_i$ 之间的路径分为两条边，即：

上行边，从 $S_i$ 到 $LCA(S_i,T_i)$ 。
下行边，从 $LCA(S_i,T_i)$ 到 $T_i$ (不包含 $LCA(S_i,T_i)$ )。

对于任意一个上行边上的点 $u$ ，如果要被观察到，都要满足以下条件：

dep[S_i]-dep[u]=w[u]

同理，对于任意一个下行边上的点 $u$ ，如果要被观察到，应满足以下条件：

dep[S_i]+dep[u]-2\times dep[LCA(S_i,T_i)]=w[u]

把含有 $u$ 的移到同一边，得到以下两式：

dep[S_i]=dep[u]+w[u]

2\times dep[LCA(S_i,T_i)]-dep[S_i]=dep[u]-w[u]

由于左式都为定值，所以我们可以建立两个存储右式值的桶，分别把左式插入两个桶中，就能快速统计满足条件的个数。

由于一个一个点遍历复杂度过高，采用树上差分的方法，具体实现如下：

对于 $S_i$ 这个点，加一个类型为 $deep[S_i]$ 的贡献，同理，对于 $T_i$ 这个点，加一个类型为 $dep[S_i]-2\times dep[LCA(S_i,T_i)]$ 的贡献；

接着在上行边和下行边的另一边减去这个贡献，即 $fa[LCA][0]$ ，减去一个类型为 $deep[S_i]$ 的贡献，对于 $LCA$ ，减去一个类型为 $dep[S_i]-2\times dep[LCA(S_i,T_i)]$ 的贡献。

这些在输入时可以先用一个邻接表保存好，后来 $dfs$ 求子树和时，就可以直接调用邻接表来加减贡献，由于用桶来记录次数，所以在开始访问点时保存好桶内装的次数，在回溯时再用桶里已经被更新的次数减去之前的次数，就是这个点为根的子树的次数。

需要注意的是，在访问每个点时，当前点对应的值为 $dep[u]+w[u]$ 和 $dep[u]-w[u]$ ，而 $dep[u]-w[u]$ 可能小于 $0$ ，所以在用桶装时，向右平移下标。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int a[301010],b[301010];//存每个点对应的值
int num1[601010],num2[601010];//装值的桶
int head1[301010],cnt;//存树的邻接表
int head2[301010],tot;//存值的邻接表
int dep[301010],fa[301010][21];//lca
int ans[301010];//答案
struct node
{
	int next;
	int to;
}e[601010];
struct number
{
	int next;
	int id;//桶装的值
	int k;//差分的值，1或-1
	int flag;//上行边或下行边
}q[1201010];
void add_edge(int from,int to)
{
	e[++cnt].next=head1[from];
	e[cnt].to=to;
	head1[from]=cnt;
}
void add_num(int from,int id,int k,int flag)
{
	q[++tot].next=head2[from];
	q[tot].id=id;
	q[tot].k=k;
	q[tot].flag=flag;
	head2[from]=tot;
}
void dfs(int u,int f)
{
	fa[u][0]=f;
	for(int i=head1[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==f)
			continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
}
void solve(int u,int fa)
{
	int s1=num1[a[u]];
	int s2=num2[b[u]+300000];//当前这个点在桶中对应的值
	for(int i=head2[u];i;i=q[i].next)
	{
		int v=q[i].id;
		if(q[i].flag==1)
			num1[v]+=q[i].k;
		else
			num2[v+300000]+=q[i].k;
	}//访问存储差分操作的邻接表，更新桶内的值
	for(int i=head1[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		solve(v,u);
	}//递归访问
	int t1=num1[a[u]];
	int t2=num2[b[u]+300000];//记录回溯此点时桶内的值
	ans[u]+=(t1-s1)+(t2-s2);//差值就是子树的次数
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dep[1]=1;
	dfs(1,0);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	for(int i=1;i<=n;i++)
	{
		int w;
		scanf("%d",&w);
		a[i]=dep[i]+w;
		b[i]=dep[i]-w;//a,b存储每个点的类型
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int LCA=lca(x,y);
		int len=dep[x]+dep[y]-2*dep[LCA];
		add_num(x,dep[x],1,1);//在x处，以dep[x]的类型装入桶，个数加1
		add_num(fa[LCA][0],dep[x],-1,1);//类似于上
		add_num(y,dep[y]-len,1,2);//在y处，以2*dep[lca]-dep[x]的类型装入桶，个数加1
		add_num(LCA,dep[y]-len,-1,2);
	}
	solve(1,0);
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}