题意:

小H正在玩一个战略类游戏,她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸
敌国的城市形成了一棵树,小H会依次进行Q次轰炸,每次会选择一个城市A进行轰炸,和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数),轰炸结束后,小H还想知道当前城市A受损的次数
作为游戏的开发者之一,你有义务回答小H的问题


题解:

考虑每个点对其他点的影响,当我们将任意一点设为跟后,由于每个点的父亲只有一个,那么当攻击某个点后,该点对他的父亲节点即父亲节点的父亲节点的影响都可以O(1)的更新 所以我们设dp[i][j]。表示i节点能向下攻击的范围,所以图片说明
即为所求


代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}

int n,q,f[maxn],dp[maxn][3];
VI G[maxn];
void dfs(int u,int fa){
    f[u]=fa;
    for(int v:G[u]) if(v!=fa){
        dfs(v,u);
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(1,0);
    while(q--){
        int x;scanf("%d",&x);

        dp[x][1]++;dp[x][2]++;
        dp[f[x]][0]++;dp[f[f[x]]][0]++;

        dp[f[x]][1]++;

        printf("%d\n",dp[x][0]+dp[f[x]][1]+dp[f[f[x]]][2]);
    }
}