题目描述
小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一一棵包含 n个结点和 n-1条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。
现在有m个玩家,第ii个玩家的起点为 ,终点为
。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)
小c想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点jj的观察员会选择在第秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第
秒也理到达了结点 j 。 小C想知道每个观察员会观察到多少人?
注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点j作为终点的玩家: 若他在第秒前到达终点,则在结点jj的观察员不能观察到该玩家;若他正好在第
秒到达终点,则在结点j的观察员可以观察到这个玩家。
输入输出格式
输入格式：
第一行有两个整数n和m 。其中n代表树的结点数量, 同时也是观察员的数量, m代表玩家的数量。
接下来 n- 1行每行两个整数u和 v,表示结点 u到结点 v有一条边。
接下来一行 n个整数,其中第j个整数为 , 表示结点j出现观察员的时间。
接下来 m行,每行两个整数,和
,表示一个玩家的起点和终点。
对于所有的数据,保证,
。
输出格式：
输出1行 n个整数,第j个整数表示结点j的观察员可以观察到多少人。
个人思路：
- 类似"雨天的尾巴"，在dfs的过程中合并数据即可。可以注意到W范围较大，且区间具有可合并性（非最大/小值等操作）.
- 因此，可利用vector维护每个点上"玩家"的增加/减少情况，再在dfs的过程中利用全局数组合并即可.
- 具体地说，对于每个玩家，分成两段分别考虑，即S->LCA和LCA->T。可以发现，在第一种情况下满足W[x]-d[x]=d[s]；在第二种情况下满足W[x]-d[x]=d[s]-2*d[lca(s,t)].
- 代入树上差分的基本过程中可以发现：在第一种情况下，利用区间合并使得lca(s,t)与s之间的点可以利用该情况的数据，第二种情况同理。当然，也可以直接用两个局部变量cnt1,cnt2分别维护W[x]-d[x],W[x]+d[x]，并在一次dfs中求得结果.
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
struct Edge{
int from,to,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
int dep[MAXN],f[MAXN][21];
void dfs_Lca(int x){
dep[x]=dep[f[x][0]]+1;
for(int i=1;i<=20;i++){
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(!dep[v]){
f[v][0]=x;
dfs_Lca(v);
}
}
}
int lca(int a,int b){
if(dep[a]>dep[b])swap(a,b);
for(int i=20;i>=0;i--){
if(dep[b]-(1<<i)>=dep[a])b=f[b][i];
}
if(a==b)return a;
for(int i=20;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
int w[MAXN];
struct player{
int s,t;
}players[MAXN];
struct item{
int pos,value;
};
vector<item> vecs_First[MAXN];
int c[MAXN],ans[MAXN];
void dfs_Solve_First(int x){
int cnt=c[w[x]+dep[x]];
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(v!=f[x][0]){
dfs_Solve_First(v);
}
}
while(!vecs_First[x].empty()){
item nowItem=vecs_First[x].back();vecs_First[x].pop_back();
int nowPos=nowItem.pos,nowValue=nowItem.value;
c[nowPos]+=nowValue;
}
ans[x]+=c[w[x]+dep[x]]-cnt;
}
void init(){
memset(c,0,sizeof(c));
}
vector<item> vecs_Second[MAXN];
void dfs_Solve_Second(int x){
int cnt=c[w[x]-dep[x]];
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(v!=f[x][0]){
dfs_Solve_Second(v);
}
}
while(!vecs_Second[x].empty()){
item nowItem=vecs_Second[x].back();vecs_Second[x].pop_back();
int nowPos=nowItem.pos,nowValue=nowItem.value;
c[nowPos]+=nowValue;
}
ans[x]+=c[w[x]-dep[x]]-cnt;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
f[1][0]=0;
dfs_Lca(1);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&players[i].s,&players[i].t);
vecs_First[players[i].s].
push_back(item{dep[players[i].s],1});
vecs_First[f[lca(players[i].s,players[i].t)][0]].
push_back(item{dep[players[i].s],-1});
vecs_Second[players[i].t].
push_back(item{dep[players[i].s]-2*dep[lca(players[i].s,players[i].t)],1});
vecs_Second[lca(players[i].s,players[i].t)].
push_back(item{dep[players[i].s]-2*dep[lca(players[i].s,players[i].t)],-1});
}
dfs_Solve_First(1);
init();
dfs_Solve_Second(1);
for(int i=1;i<=n-1;i++){
cout<<ans[i]<<" ";
}
printf("%d
",ans[n]);
return 0;
}