我们读题,发现,每次轰炸只对距离不超过2的点造成影响,那么,我们可以考虑,直接计算每个距离x不超过2的点对x造成的贡献。
于是,我们初步考虑,对于每个x,我们将所有距离x不超过2的点的答案加1即可
但,不难发现,这是很容易被卡的,举个例子如果一棵树中2-n的父亲都是1的话,那么,每有一个点被轰炸,我们就要将所有点的答案加一,复杂度就会飙升到。
我们注意到,有如下点会对x造成贡献:
距离0:x本身
距离1:x的父亲和儿子
距离2:x的爷爷和兄弟和孙子
我们发现,复杂度的问题在于,一个点的儿子,孙子,兄弟可能很多,但,父亲和爷爷只有一个,所以,我们考虑下,我们每次,只暴力将贡献上传给父亲和爷爷,这样,对于父亲和爷爷,他们的儿子/孙子的贡献其实一开始就算好了。
然后,我们考虑下如何算父亲和爷爷的贡献,这个就很简单了,因为父亲和爷爷只有一个,所以,我们只需要暴力统计父亲和爷爷加了几次即可~
难点在于,如何算兄弟的贡献。
我们设表示一次轰炸后,自己/儿子/孙子波及到i点且还剩距离j可以波及的轰炸的次数
那么,明显,兄弟的贡献,一定是保存在了当中的,不过,里面有一个是自己波及的,所以答案加上即可
代码:
#include<bits/stdc++.h> using namespace std; const int N=75e4+1; struct node{ int v,nex; }t[N<<1]; int sum[N][3],fa[N]; int len,las[N]; inline void add(int u,int v){ t[++len]=(node){v,las[u]},las[u]=len; } inline void dfs(int now){ for(int i=las[now];i;i=t[i].nex){ int v=t[i].v; if(v!=fa[now]){ fa[v]=now; dfs(v); } } } inline int calc(int x){ int ans=sum[x][0]+sum[x][1]+sum[x][2];//儿子波及给x的 if(fa[x]){ ans+=(sum[fa[x]][2]);//父亲波及 ans+=(sum[fa[x]][1]-sum[x][2]);//兄弟波及 } if(fa[fa[x]]){ ans+=sum[fa[fa[x]]][2];//爷爷波及 } return ans; } int main(){ int n,Q; scanf("%d%d",&n,&Q); for(int i=1;i<n;++i){ int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); } dfs(1); while(Q--){ int x; scanf("%d",&x); ++sum[x][2]; if(fa[x]){ ++sum[fa[x]][1]; } if(fa[fa[x]]){ ++sum[fa[fa[x]]][0]; } printf("%d\n",calc(x)); } return 0; }