- 给定一棵树，第(i)个点在第(w_i)个时刻会有一个观察员。
- 有(m)个人在跑步，沿着从(x)到(y)的树上路径，每单位时间跑过一条边。
- 问每个观察员能看到多少人。
- (nle3 imes10^5)
路径的拆分
考虑(x ightarrow LCA(x,y))的路径，经过点的深度与时间依次为((dep_x,0),(dep_x-1,1),(dep_x-2,2),...)。
容易发现，深度与时间之和为定值。
同理考虑(LCA(x,y) ightarrow y)的路径，经过点的深度与时间之差就应该是一个定值。
所以我们可以把一条路径拆成两部分（注意(LCA(x,y))只应算到一部分中，否则会重复计算）。
这样一来暴力的方法就是对每个点维护两个数组，分别统计时间+深度=(i)的点数和时间-深度=(i)的点数。
线段树合并
考虑这是一个静态的路径修改问题，所以可以树上差分。
既然涉及树上差分，自然需要子树信息合并。
合并若干节点的数组，自然可以用线段树合并。
于是这道题就自然地做完了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 300000
#define LN 20
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,w[N+5],ans[N+5],ee,lnk[N+5],X[N+5],Y[N+5];
struct edge {int to,nxt;}e[2*N+5];
class SegmentTree
{
private:
int Nt,Rt[N+5];struct node {int V,S[2];}O[N*30];
I void U(int& rt,CI p,CI v,CI l,CI r)//单点修改
{
if(!rt&&(rt=++Nt),O[rt].V+=v,l==r) return;RI mid=l+r>>1;
p<=mid?U(O[rt].S[0],p,v,l,mid):U(O[rt].S[1],p,v,mid+1,r);
}
I void Merge(int& x,CI y,CI l,CI r)//线段树合并
{
if(!x||!y) return (void)(x|=y);if(l==r) return (void)(O[x].V+=O[y].V);RI mid=l+r>>1;
Merge(O[x].S[0],O[y].S[0],l,mid),Merge(O[x].S[1],O[y].S[1],mid+1,r);
}
I int Q(CI rt,CI p,CI l,CI r)//单点询问
{
if(l==r) return O[rt].V;RI mid=l+r>>1;
return p<=mid?Q(O[rt].S[0],p,l,mid):Q(O[rt].S[1],p,mid+1,r);
}
public:
I void C()//清空
{
for(RI i=1;i<=Nt;++i) O[i].V=O[i].S[0]=O[i].S[1]=0;Nt=0;
for(RI i=0;i<=2*n;++i) Rt[i]=0;
}
I void U(CI x,CI p,CI v) {U(Rt[x],p,v,1,n<<1);}
I void Merge(CI x,CI y) {Merge(Rt[x],Rt[y],1,n<<1);}
I int Q(CI x,CI p) {return Q(Rt[x],p,1,n<<1);}
}S;
namespace Tree
{
int dep[N+5],fa[N+5][LN+1];
I void Init(CI x=1,CI lst=0)//初始化
{
RI i;for(i=1;i<=LN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&
(dep[e[i].to]=dep[fa[e[i].to][0]=x]+1,Init(e[i].to,x),0);
}
I int LCA(RI x,RI y)//倍增LCA
{
RI i;dep[x]<dep[y]&&(x^=y^=x^=y);
for(i=0;dep[x]^dep[y];++i) (dep[x]^dep[y])>>i&1&&(x=fa[x][i]);if(x==y) return x;
for(i=LN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);return fa[x][0];
}
I void dfs1(CI x=1,CI lst=0)//时间+深度为定值
{
for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(dfs1(e[i].to,x),S.Merge(x,e[i].to),0);
ans[x]=S.Q(x,w[x]+dep[x]);
}
I void dfs2(CI x=1,CI lst=0)//时间-深度为定值
{
for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(dfs2(e[i].to,x),S.Merge(x,e[i].to),0);
ans[x]+=S.Q(x,w[x]-dep[x]+n);
}
}
int main()
{
using namespace Tree;
RI i,x,y,z,d;for(scanf("%d%d",&n,&m),i=1;i^n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for(i=1;i<=n;++i) scanf("%d",w+i);dep[1]=1,Init();
for(i=1;i<=m;++i) scanf("%d%d",X+i,Y+i);
for(i=1;i<=m;++i) z=LCA(x=X[i],y=Y[i]),S.U(x,dep[x],1),S.U(fa[z][0],dep[x],-1);dfs1(),S.C();//x->LCA
for(i=1;i<=m;++i) z=LCA(x=X[i],y=Y[i]),d=dep[x]+dep[y]-(dep[z]<<1),S.U(y,d-dep[y]+n,1),S.U(z,d-dep[y]+n,-1);//LCA的儿子->y
for(dfs2(),i=1;i<=n;++i) printf("%d%c",ans[i],"
"[i==n]);return 0;//输出答案
}