题目
题目链接：https://www.luogu.com.cn/problem/P1600
小c 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一一棵包含 \(n\) 个结点和 \(n-1\) 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 \(1\) 到 \(n\) 的连续正整数。
现在有 \(m\) 个玩家，第 \(i\) 个玩家的起点为 \(s_i\)，终点为 \(t_i\)。每天打卡任务开始时，所有玩家在第 \(0\) 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)
小c 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 \(j\) 的观察员会选择在第 \(w_j\) 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 \(w_j\) 秒也正好到达了结点 \(j\) 。小c 想知道每个观察员会观察到多少人?
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。 即对于把结点 \(j\) 作为终点的玩家：若他在第 \(w_j\) 秒前到达终点,则在结点 \(j\) 的观察员不能观察到该玩家；若他正好在第 \(w_j\) 秒到达终点,则在结点 \(j\) 的观察员可以观察到这个玩家。
思路
将一条路径拆分为往上个往下两条，设这条路径的起点与终点分别是 \(u,v\)，他们的 \(\operatorname{LCA}\) 为 \(p\)，假设一个点 \(x\)：
- 上行的路可以对 \(x\) 造成贡献当且仅当 \(dep[u]-dep[x]=w_x\)，移项得 \(dep[u]=w_x+dep[x]\)。
- 下行的路可以对 \(x\) 造成贡献当且仅当 \(dis(u,v)-(dep[v]-dep[x])=w_x\)，移项得 \(dep[u]-2dep[p]=w_x-dep[x]\)。
发现等号左边全部是定值，等号右边全部和 \(x\) 有关，喜闻乐见线段树合并即可。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=600010,LG=20,QWQ=300010;
int n,m,tot,ans[N],a[N],rt1[N],rt2[N],head[N],dep[N],f[N][LG+1];
vector<int> del1[N],del2[N];
struct edge
{
int next,to;
}e[N*2];
void add(int from,int to)
{
e[++tot].to=to;
e[tot].next=head[from];
head[from]=tot;
}
struct SegTree
{
int tot,lc[N*LG*4],rc[N*LG*4],cnt[N*LG*4];
void pushup(int x)
{
cnt[x]=cnt[lc[x]]+cnt[rc[x]];
}
int update(int x,int l,int r,int k,int v)
{
if (!x) x=++tot;
if (l==k && r==k)
{
cnt[x]+=v;
return x;
}
int mid=(l+r)>>1;
if (k<=mid) lc[x]=update(lc[x],l,mid,k,v);
else rc[x]=update(rc[x],mid+1,r,k,v);
pushup(x);
return x;
}
int merge(int x,int y)
{
if (!x || !y) return x+y;
cnt[x]=cnt[x]+cnt[y];
lc[x]=merge(lc[x],lc[y]);
rc[x]=merge(rc[x],rc[y]);
return x;
}
int query(int x,int l,int r,int k)
{
if (!x) return 0;
if (l==r) return cnt[x];
int mid=(l+r)>>1;
if (k<=mid) return query(lc[x],l,mid,k);
else return query(rc[x],mid+1,r,k);
}
}seg1,seg2;
void dfs1(int x,int fa)
{
dep[x]=dep[fa]+1; f[x][0]=fa;
for (int i=1;i<=LG;i++)
f[x][i]=f[f[x][i-1]][i-1];
for (int i=head[x];~i;i=e[i].next)
if (e[i].to!=fa) dfs1(e[i].to,x);
}
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (int i=LG;i>=0;i--)
if (dep[f[x][i]]>=dep[y]) x=f[x][i];
if (x==y) return x;
for (int i=LG;i>=0;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void dfs2(int x)
{
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=f[x][0])
{
dfs2(v);
rt1[x]=seg1.merge(rt1[x],rt1[v]);
rt2[x]=seg2.merge(rt2[x],rt2[v]);
}
}
if (a[x]+dep[x]<=n)
ans[x]+=seg1.query(rt1[x],1,n+QWQ,a[x]+dep[x]+QWQ);
ans[x]+=seg2.query(rt2[x],1,n+QWQ,a[x]-dep[x]+QWQ);
for (int i=0;i<del1[x].size();i++)
rt1[x]=seg1.update(rt1[x],1,n+QWQ,del1[x][i],-1);
for (int i=0;i<del2[x].size();i++)
rt2[x]=seg2.update(rt2[x],1,n+QWQ,del2[x][i],-1);
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs1(1,0);
for (int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
int p=lca(u,v);
rt1[u]=seg1.update(rt1[u],1,n+QWQ,dep[u]+QWQ,1);
rt2[v]=seg2.update(rt2[v],1,n+QWQ,dep[u]-dep[p]*2+QWQ,1);
del1[p].push_back(dep[u]+QWQ);
del2[p].push_back(dep[u]-dep[p]*2+QWQ);
if (a[p]==dep[u]-dep[p]) ans[p]--;
}
dfs2(1);
for (int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}