本文主要是介绍[noip2016]天天爱跑步,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
小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\n",ans[n]);return 0;
}
这篇关于[noip2016]天天爱跑步的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!