小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一棵包含 n个结点和n−1条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。
现在有m个玩家,第i个玩家的起点为 (S_i),终点为(T_i)。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)
小c想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。在结点j的观察员会选择在第(W_j)秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第(W_j)秒也理到达了结点j。小C想知道每个观察员会观察到多少人?
注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点jj作为终点的玩家:若他在第(W_j)秒前到达终点,则在结点jj的观察员不能观察到该玩家;若他正好在第(W_j)秒到达终点,则在结点jj的观察员可以观察到这个玩家。
刚开始拿到这道题直接毫无头绪，但是思路其实挺简单的
首先我们可以把每一条路径拆成起点到lca的上行路和lca到终点的下行路这两条路径
对于每条上行路，节点i可以看作从i这个点出发向下走(w_i)步，也就是当(dep_s-dep_i=w_i)时，i点会产生贡献
而对于每条下行路，节点i可以看作从i出发向上走(w_i)步，也就是当(len(s,t)-dep_t+dep_i=w_i)，i点会产生贡献
于是我们开一个桶记录一下贡献，再减掉没有产生贡献的部分和减去一次多算了的lca的贡献就可以了
因为每次计算的贡献是以s为起点或以t为终点，而更新贡献的时候是从叶子往上更新的，所以要减掉lca的贡献
然后对于每个人，只有在(dep_s=dep_lca+w_lca)的情况下才会多算lca的答案，减去多算的一次即可
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 3e5;
using namespace std;
struct player
{
int s,t,lca,len;
}p[N + 5];
int n,m,w[N + 5],ans[N + 5],c[N * 2 + 5],s[N + 5];
int dep[N + 5],size[N + 5],son[N + 5],top[N + 5],fa[N + 5];
vector <int> d[N + 5],sl[N + 5],tl[N + 5],ll[N + 5];
void dfs1(int u,int f)
{
dep[u] = dep[f] + 1;
size[u] = 1;
fa[u] = f;
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
if (v == f)
continue;
dfs1(v,u);
size[u] += size[v];
if (size[v] > size[son[u]])
son[u] = v;
}
}
void dfs2(int u,int to)
{
top[u] = to;
if (son[u])
dfs2(son[u],to);
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
if (v != fa[u] && v != son[u])
dfs2(v,v);
}
}
int get_lca(int x,int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x,y);
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x,y);
return x;
}
void dfs3(int u)
{
int goal = dep[u] + w[u],res = c[goal];
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
if (v == fa[u])
continue;
dfs3(v);
}
c[dep[u]] += s[u];
ans[u] += c[goal] - res;
for (int i = 0;i < sl[u].size();i++)
c[dep[sl[u][i]]]--;
}
void dfs4(int u)
{
int goal = w[u] - dep[u] + N,res = c[goal];
vector <int>::iterator it;
for (it = d[u].begin();it != d[u].end();it++)
{
int v = (*it);
if (v == fa[u])
continue;
dfs4(v);
}
for (int i = 0;i < ll[u].size();i++)
c[ll[u][i] + N]++;
ans[u] += c[w[u] - dep[u] + N] - res;
for (int i = 0;i < tl[u].size();i++)
c[tl[u][i] + N]--;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for (int i = 1;i < n;i++)
{
scanf("%d%d",&u,&v);
d[u].push_back(v);
d[v].push_back(u);
}
for (int i = 1;i <= n;i++)
scanf("%d",&w[i]);
dfs1(1,0);
dfs2(1,1);
for (int i = 1;i <= m;i++)
{
scanf("%d%d",&p[i].s,&p[i].t);
p[i].lca = get_lca(p[i].s,p[i].t);
s[p[i].s]++;
p[i].len = dep[p[i].s] + dep[p[i].t] - 2 * dep[p[i].lca];
sl[p[i].lca].push_back(p[i].s);
tl[p[i].lca].push_back(p[i].len - dep[p[i].t]);
ll[p[i].t].push_back(p[i].len - dep[p[i].t]);
}
dfs3(1);
dfs4(1);
for (int i = 1;i <= m;i++)
if (dep[p[i].s] == dep[p[i].lca] + w[p[i].lca])
ans[p[i].lca]--;
for (int i = 1;i <= n;i++)
printf("%d ",ans[i]);
return 0;
}