0.前言
参考Treaker的题解把这道据说史上最毒瘤的题A了qwq
1.题意简述
给定一棵树和(m)条路径，分别求出在(w_i)时刻恰好到达(i)的人数。
2.解法
设当前路径为((S,T))，考虑被观察到的条件。
这种树上路径的一般性套路是拆成((S,LCA))和((LCA,T))两条链分别考虑，我们也采取这种方法：
1.观察员(now)在((S,LCA))上，则有(dep[S]-dep[now]=w[now])，即(dep[now]+w[now]=dep[S])；
2.观察员在((LCA,T))上，则有(dep[now]=dep[T]-(dis(S,T)-w[now]))，即(w[now]-dep[now]=dis(S,T)-dep[T])。
统计上，我们对这两个式子各开一个桶，记录右边的，查询左边的。即以下统计代码：
bup[dep[now]]+=cnt[now];
for(rg int i=0;i<pat[now].size();i++){
int fuckccf=pat[now][i];//只是个临时变量...
bdn[p[fuckccf].dis-dep[p[fuckccf].t]+300000]++;
}
其中bup和bdn是两个桶，p是路径结构体，pat是以每个点为终点的路径编号vector。
注意到统计bdn时有一个+300000，原因是(w[now]-dep[now])可能越界（深度(<0)）。
需要处理的亿些细节：
1.统计时应只考虑新增的值，可以先将计算之前的桶值记录下来：
int up=bup[dep[now]+w[now]],dn=bdn[w[now]-dep[now]+300000];//提前记录
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=f[now][0])Calc(v);
}
...
ans[now]+=bup[dep[now]+w[now]]-up+bdn[w[now]-dep[now]+300000]-dn;
2.统计完回溯时要将以该点为(LCA)的路径产生的贡献去除，即：
for(rg int i=0;i<lca[now].size();i++){
int fuckccf=lca[now][i];//......
bup[dep[p[fuckccf].s]]--;
bdn[p[fuckccf].dis-dep[p[fuckccf].t]+300000]--;
}
其中lca的定义与pat几乎相同，从名字可以猜出意思。
3.端点是(LCA)的路径（可以理解为不拐弯）的(LCA)会被多算，应在一开始减去：
if(dep[p[i].s]==dep[p[i].lca]+w[p[i].lca])ans[p[i].lca]--;
3.代码
无注释版本（缺省源在码风整理那篇里）：
#define N 300010
int n,m,w[N],ans[N];
int bup[N],bdn[N+N],cnt[N];
struct Edge {
int to,nxt;
}e[N<<1];
int head[N],tot;
inline void ade(int u,int v){
e[++tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
}
struct Path {
int s,t,lca,dis;
}p[N];
int f[N][20],dep[N];
void DFS(int now,int ff){
dep[now]=dep[ff]+1;
f[now][0]=ff;
for(rg int i=1;i<20;i++){
f[now][i]=f[f[now][i-1]][i-1];
}
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
DFS(v,now);
}
}
}
inline int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(rg int i=19;i>=0;i--){
if(dep[f[u][i]]>=dep[v]){
u=f[u][i];
}
}
if(u==v)return u;
for(rg int i=19;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i],v=f[v][i];
}
}
return f[u][0];
}
vector<int>pat[N];
vector<int>lca[N];
void Calc(int now){
int up=bup[dep[now]+w[now]],dn=bdn[w[now]-dep[now]+300000];
for(rg int i=head[now];i;i=e[i].nxt){
int v=e[i].to;
if(v!=f[now][0])Calc(v);
}
bup[dep[now]]+=cnt[now];
for(rg int i=0;i<pat[now].size();i++){
int fuckccf=pat[now][i];
bdn[p[fuckccf].dis-dep[p[fuckccf].t]+300000]++;
}
ans[now]+=bup[dep[now]+w[now]]-up+bdn[w[now]-dep[now]+300000]-dn;
for(rg int i=0;i<lca[now].size();i++){
int fuckccf=lca[now][i];
bup[dep[p[fuckccf].s]]--;
bdn[p[fuckccf].dis-dep[p[fuckccf].t]+300000]--;
}
}
int main(){
Read(n),Read(m);
for(rg int i=1;i<n;i++){
int u,v;
Read(u),Read(v);
ade(u,v),ade(v,u);
}
DFS(1,0);
for(rg int i=1;i<=n;i++)Read(w[i]);
for(rg int i=1;i<=m;i++){
Read(p[i].s),Read(p[i].t);
p[i].lca=LCA(p[i].s,p[i].t);
p[i].dis=dep[p[i].s]+dep[p[i].t]-2*dep[p[i].lca];
cnt[p[i].s]++,pat[p[i].t].push_back(i),lca[p[i].lca].push_back(i);
if(dep[p[i].s]==dep[p[i].lca]+w[p[i].lca])ans[p[i].lca]--;
}
Calc(1);
for(rg int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
4.总结
毒瘤死了基础算法组合起来也可以很难啊……所以注重融会贯通吧~