D-小H和游戏

这个题解实话说都是抄的其他dl的题解
写这个的用意主要是为了便于自己理解以及把dl觉得显而易见的写出来

前导
一:
整合树，建立数组fa[N]来确定每个点的父节点
Method one: vector

vector<int> q[N];
inline void dfs(int x, int f) {//确定父节点
    fa[x] = f;
    for (auto i : q[x]) { 
        if (i == f) continue;
        else dfs(i, x);
    }
        //for(auto i:q[x]) --> vector<int>::iterator it; 
        //for(it=q[x].begin();it!=q[x].end();++it) 大概便于理解就是这意思了
}
inline void init() {
    for(int i=1;i<n;++i) {
        int x, y;
        cin >> x >> y;
        q[x].push_back(y); //存储与x相邻的点
        q[y].push_back(x); //存储与y相邻的点
    }
}

Method two : 前向星（等会儿补）

二:
解释数据中部分变量意思
cnt[x][0] --> x本身
cnt[x][1] --> x儿子
cnt[x][2] --> x儿子的儿子
求点x被波及到次数可化为: cnt[x][0]+cnt[fa[x]][1]+cnt[fa[fa[x]]][2]
x被波及大致有以下：
x本身，x儿子，x儿子的儿子，x父亲，x的父亲的父亲，x的兄弟（x父亲的儿子）

假使轰炸x的儿子y,则x被波及可表述为 ++cnt[fa[y]][0]-->++cnt[x][0]
假使轰炸x的孙子z,则x被波及可表述为 ++cnt[fa[fa[z]]][0]-->++cnt[x][0]
-->轰炸儿子孙子可直接在cnt[x][0]中反映出来
假使轰炸x的父亲r,则x被波及可表述为 ++cnt[r][1]-->++cnt[fa[x]][1]
假使轰炸x的爷爷g,则x被波及可表述为 ++cnt[g][2]-->++cnt[fa[fa[x]]][2]
假使轰炸x的兄弟v,则x被波及可表述为 x(v父亲的儿子) ++cnt[fa[x]][1]
计算代码：

while (m--) {
        int x;
        cin >> x;
        //cnt[x][0]--本身 cnt[x][1]--儿子 cnt[x][2]--儿子的儿子
        ++cnt[x][1], ++cnt[x][2];   //x的儿子被波及，x的儿子的儿子被波及
        ++cnt[fa[x]][0], ++cnt[fa[x]][1];  //x的父亲被波及，x父亲的儿子被波及(包括x)
        ++cnt[fa[fa[x]]][0];  //x的父亲的父亲被波及
        cout << cnt[x][0] + cnt[fa[x]][1] + cnt[fa[fa[x]]][2] << "\n"; 
    }         

三:
总代码

#pragma warning (disable :4996)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-10;
#define For(i,n,m) for(int i=n;i<=m;++i)

const int N = 75e4 + 10;
int n, m, a[N], fa[N];
int cnt[N][3];
vector<int> q[N];
inline void dfs(int x, int f) {//确定父节点
    fa[x] = f;
    for (auto i : q[x]) {
        if (i == f) continue;
        else dfs(i, x);
    }
}
inline void init() {
    cin >> n >> m;
    For(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        q[x].push_back(y);
        q[y].push_back(x);
    }
}
inline void solve() {
    dfs(1, 0);
    while (m--) {
        int x;
        cin >> x;
        //cnt[x][0]--本身 cnt[x][1]--儿子 cnt[x][2]--儿子的儿子
        ++cnt[x][1], ++cnt[x][2];   
        ++cnt[fa[x]][0], ++cnt[fa[x]][1]; 
        ++cnt[fa[fa[x]]][0]; 
        cout << cnt[x][0] + cnt[fa[x]][1] + cnt[fa[fa[x]]][2] << "\n"; 
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    init();
    solve();
    return 0;
}