牛客 小H和游戏

考虑到一个节点的儿子孙子和兄弟可能有多个，但是父节点和祖父节点只有一个，所以我们把不断累加的答案放进它的父节点和祖父节点中去，然后在需要计算时，再通过父节点和祖父节点，把答案加回来即可。

定义sum[u][i]:u节点受到波及的次数，且可以向外延伸i个单位长度。

对于每次轰炸，我们进行如下操作：

1.sum[u][2]++，sum[f[u]][1]++,sum[f[f[u]][0]++。 （若无父节点或祖父节点则省略）

2.ans=sum[u][2]+sum[u][1]+sum[u][0] （孙子，儿子，和自己给u节点带来的影响）

3.ans+=sum[f[f[u]]][2] （祖父节点带来的影响，如无祖父节点则省略）

4.ans+=sum[f[u]][2] （父节点带来的影响，若无父节点则省略）

5.ans+=sum[f[u]][1]-sum[u][2] （兄弟节点带来的影响，若无兄弟节点则省略。这里为什么需要减去sum[u][2]呢，因为u之前的操作sum[f[u]][1]++，导sum[f[u]][1]多加了sum[u][2]次，所以需要减去，即：sum[f[u]][1]中包含了sum[u][2]它自己的贡献，而它自己，不是它的兄弟！）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,q,u,v,ans;
int sum[N][3],f[N];
int cnt,head[N];
struct edge{int next,to;}e[N<<1];

inline void add(int u,int v)
{
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void dfs(int u,int fa)
{
    for (register int i=head[u]; i; i=e[i].next)
    if (e[i].to!=fa)
    {
        f[e[i].to]=u;
        dfs(e[i].to,u);
    }
}

signed main(){
    scanf("%lld%lld",&n,&q);
    for (register int i=1; i<n; ++i) scanf("%lld%lld",&u,&v),add(u,v),add(v,u);
    dfs(1,0);
    while (q--)
    {
        scanf("%lld",&u);
        sum[u][2]++; if (f[u]) sum[f[u]][1]++; if (f[f[u]]) sum[f[f[u]]][0]++;
        ans=0;
        ans=sum[u][2]+sum[u][1]+sum[u][0];
        if (f[u]) ans+=sum[f[u]][2],ans+=sum[f[u]][1]-sum[u][2];
        if (f[f[u]]) ans+=sum[f[f[u]]][2];
        printf("%lld\n",ans);
    }
return 0;
}