题目大概意思是这样的,我们有一颗树,有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; }