链接：https://ac.nowcoder.com/acm/contest/5203/D
来源：牛客网

题目描述

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

输入

4 4 
1 2 
2 3 
3 4 
1 
2 
3 
4

输出

1 
2 
3 
3

首先先建图，然后把无根树转成有根树，把森林转成一棵树（全是爸爸），更新 f a fa fa数组，然后开三个数组分别存轰炸一个点对其他点的影响。注意根据题意要分三次，因为本题中轰炸会对上下两代和兄弟都造成影响，所以一个数组存对兄弟的影响，一个数组存对父亲，父亲的父亲的影响，另一个倒着存父亲和父亲的父亲对儿子的影响。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=750007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N];

ll fa[N];//存父节点
ll bo[N];//兄弟，兄弟对兄弟的贡献
ll ba[N];//孩子//父亲结点和父亲的父亲结点对孩子结点的贡献
ll gr[N];//长辈//孩子结点对父亲结点和父亲的父亲结点的贡献
vector<ll>G[N];
void dfs(ll u,ll f)//全是爸爸
{
    fa[u]=f;
    ll len=G[u].size();
    over(i,0,len-1)
    {
        ll v=G[u][i];
        if(v==f)continue;
        dfs(v,u);
    }
}
ll q,u,v;
int main()
{
    scanf("%lld%lld",&n,&q);
    over(i,1,n-1)
    {
        scanf("%lld%lld",&u,&v);//1~n
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    while(q--)//无根树转有根树
    {
        ll tmp;
        scanf("%lld",&tmp);
        ba[tmp]++;//必须要分开，不然会加两次
        bo[fa[tmp]]++;
        gr[fa[tmp]]++,gr[fa[fa[tmp]]]++;
        printf("%lld\n",gr[tmp]+bo[fa[tmp]]+ba[fa[tmp]]+ba[fa[fa[tmp]]]);
    }
    return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧