小H和游戏

题意：

传送门

分析：

无根树变有根树。
设置数组：\(num[v][i]\)，其中 \(0\leq i \leq 2\)。
表示：点 \(v\) 对距离点 \(v\) 距离为 \(i\) 的孩子节点产生的受损数。

代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=750050;
int fa[N],num[N][3];
vector<int>G[N];
void dfs(int v,int p)
{
    fa[v]=p;
    for(int i=0;i<G[v].size();i++)
    {
        int u=G[v][i];
        if(u==p)
            continue;
        dfs(u,v);
    }
}
int main()
{
    int n,q,u,v;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1,0);
    while(q--)
    {
        scanf("%d",&v);
        //受影响的点：
        num[v][1]++;//点v的孩子
        num[v][2]++;//点v的孙子
        num[fa[v]][1]++;//点v的兄弟
        num[fa[v]][0]++;//点v的父亲
        num[fa[fa[v]]][0]++;//点v的父亲的父亲
        printf("%d\n",num[v][0]+num[fa[v]][1]+num[fa[fa[v]]][2]);//哪些点可以对该点产生影响
    }
    return 0;
}

小H和游戏

原文：https://www.cnblogs.com/1024-xzx/p/12701963.html