我们读题,发现,每次轰炸只对距离不超过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;
}