图片说明
题目大概意思是这样的,我们有一颗树,有q次询问,每一次会轰炸给出这个点的距离不超过二的点,每一次输出当前这个点被轰炸的次数。
我们这个题目需要一些tricks,想想我们怎么样可以把每次轰炸的点的距离不超过2的点这么描述出来并且做到不重复不遗漏呢?
我们可以这样考虑,我们使用一个eff数组,eff[u][0]表示u这个点的轰炸次数,eff[u][1]表示u这个点的儿子们轰炸次数,eff[u][2]表示u这个点的孙子们轰炸次数,那么每次轰炸一个点u,需要更新的是
eff[fa[now]][0]++;//父亲节点自己
eff[fa[now]][1]++;//父亲节点的儿子们
eff[fa[fa[now]]][0]++;//爷爷节点
eff[now][1]++;//儿子节点
eff[now][2]++;//孙子节点
这里要特别注意的是很容易多写一个eff[now][0]++;
其实这个是不对的,因为如果你这样的加了的话,那么会产生重复,因为你的eff[fa[u]][1]包含了这个点。
最后输出的是eff[now][0]+eff[fa[now]][1]+eff[fa[fa[now]]][2]

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#include<string>
#include<ctime>
#include<list>
#include<bitset>
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.text","r",stdin)
#define pi acos(-1)

typedef long long ll;
using namespace std;

template<class T> bool read(T & ret)//ll,int,double,float,+/-
{
    char c;int sgn;T bit=0.1;if(c=getchar(),c==EOF) return 0;while(c!='-' && c!='.' && (c<'0' || c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0' && c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n') {ret*=sgn;return 1;}while(c=getchar(),c>='0' && c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;return 1;
}
const int N=750010;
int n,q;
vector<int> e[N];
int eff[N][3]; //
int fa[N];
void dfs(int u,int fat){
    fa[u]=fat;
    for(auto x:e[u]){
        if(x!=fat)
        dfs(x,u);
    }
}
signed main(){

    input_fast;
    cin>>n>>q;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        e[a].pb(b);
        e[b].pb(a);
    }
    dfs(1,0);
    while(q--)
    {
        int now;
        cin>>now;
        eff[fa[now]][0]++;//父亲节点自己
        eff[fa[now]][1]++;//父亲节点的儿子们
        eff[fa[fa[now]]][0]++;//爷爷节点
        eff[now][1]++;//儿子节点
        eff[now][2]++;//孙子节点

        cout<<eff[now][0]+eff[fa[now]][1]+eff[fa[fa[now]]][2]<<endl;
    }
    return 0;
}