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



京公网安备 11010502036488号