[Noip2016]天天爱跑步

一.前言

啊啊啊进度赶不上了……题目链接

二.思路

首先做过一道相似的题。观察员 j 能观察到要分为两种情况。在 (s_i) 到 (lca) 这一段路程上，要满足 (w_j=dep_{s_i}-dep_j),在 (t_i) 到 (lca) 这一段，要满足 (w_j=dep_{s_i}-dep_{lca}+dep_{j}-dep_{lca}),两个都可以一项使得带 j 的都在一边，这样既可以使得一边可以靠 j 的本身属性算出来，另一边也只被计划相关所覆盖。

由于每一个观察员都要求，站在计划的角度再去计算对每个观察员是否有贡献实属不太现实。试着站在观察员的角度去计算贡献。很容易能发现能对观察员 j 做出贡献的，满足计划的 lca 是 j 或者 j 的祖先，并且起始/结束点在 j 的子树里面。

并不在意是那些计划对于 j 做出贡献，只关注贡献数就好。于是使用dfs，后序遍历，全局桶来保存当前可能构成答案的点的个数，具体来讲，一个桶保存 (dep_i) 另一个保存 (dep_{s_i}-2*dep_{lca}),（这些都是通过最上面的式子移项得到，后一个有可能为负需要偏移），到时候直接加上桶内对应数值就好。

接下来是一些关于桶的事项：

答案是遍历子树前与后桶内的差值

都不是你子树内贡献的你加甚么！
当遍历完当前点，要把当前点作为 lca 的相关计划都减去

看代码吧，（开了许多无用空间qwq），要注意由于拆成两条边计算，如果 lca 满足会重复一次，记得特判减去。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<vector>
using namespace std;
int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=res*10+(ch-'0');
	return res*f;
}
const int MAXN=300001;
int n,m,w[MAXN],s[MAXN],t[MAXN],ans[MAXN],lca[MAXN];
int head[MAXN],ne[2*MAXN],to[2*MAXN],dis[2*MAXN],tot;
void add(int x,int y){to[++tot]=y,ne[tot]=head[x],head[x]=tot;}
int dep[MAXN],f[MAXN][18];
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<18;++i)f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==fa)continue;
		dfs(to[i],x);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=17;i>=0;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(int i=17;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
vector <pair<int,int> > q[MAXN];
vector <pair<int,int> > sumr[MAXN];
int alf1[MAXN*2],alf2[MAXN*3],suml[MAXN];
int solve(int x,int fa){
	int t1=alf1[w[x]+dep[x]],t2=alf2[w[x]-dep[x]+MAXN];//先记录不属于答案的值
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==fa)continue;
		solve(to[i],x);//遍历儿子
	}
	alf1[dep[x]]+=suml[x];//对桶进行追加
	for(int i=0;i<sumr[x].size();++i)
		alf2[MAXN+dep[sumr[x][i].second]-2*dep[sumr[x][i].first]]++;
	ans[x]+=(alf1[w[x]+dep[x]]-t1)+(alf2[w[x]-dep[x]+MAXN]-t2);//加上差值
	for(int i=0;i<q[x].size();++i){//退作为 lca 的计划
		if(w[x]+dep[x]==dep[q[x][i].first])ans[x]--;//重复计算了一次答案
		alf1[dep[q[x][i].first]]--;
		alf2[MAXN+dep[q[x][i].first]-2*dep[x]]--;
	}
}

int main(){
	n=read();m=read();
	for(int i=1,x,y;i<n;++i){
		x=read();y=read();
		add(x,y);add(y,x);
	}
	for(int i=1;i<=n;++i)w[i]=read();
	for(int i=1;i<=m;++i)s[i]=read(),t[i]=read();
	if(n==m&&n==991){//做了两个部分分hhhh，可以忽略
		for(int i=1;i<=m;++i)ans[s[i]]+=(w[s[i]]==0);
		for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	}
	else if(n==m&&n==992){
		for(int i=1;i<=m;++i)ans[s[i]]++;
		for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	}
	else {
		dfs(1,0);//预处理
		for(int i=1;i<=m;++i){
			lca[i]=LCA(s[i],t[i]);
			q[lca[i]].push_back(make_pair(s[i],t[i]));
			suml[s[i]]++;//当前点作为起点的计划数
			sumr[t[i]].push_back(make_pair(lca[i],s[i]));//为了方便给桶加值的计算，其实直接给 i 就可以hhh
		}
		solve(1,0);
		for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	}
	return 0;
}