题意:
小H正在玩一个战略类游戏,她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸
敌国的城市形成了一棵树,小H会依次进行Q次轰炸,每次会选择一个城市A进行轰炸,和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数),轰炸结束后,小H还想知道当前城市A受损的次数
作为游戏的开发者之一,你有义务回答小H的问题
题解:
考虑每个点对其他点的影响,当我们将任意一点设为跟后,由于每个点的父亲只有一个,那么当攻击某个点后,该点对他的父亲节点即父亲节点的父亲节点的影响都可以O(1)的更新 所以我们设dp[i][j]。表示i节点能向下攻击的范围,所以
即为所求
代码:
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 1e6 + 6; const LL inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} LL inv(LL x){return qp(x,mod-2);} int n,q,f[maxn],dp[maxn][3]; VI G[maxn]; void dfs(int u,int fa){ f[u]=fa; for(int v:G[u]) if(v!=fa){ dfs(v,u); } } int main(){ scanf("%d%d",&n,&q); for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs(1,0); while(q--){ int x;scanf("%d",&x); dp[x][1]++;dp[x][2]++; dp[f[x]][0]++;dp[f[f[x]]][0]++; dp[f[x]][1]++; printf("%d\n",dp[x][0]+dp[f[x]][1]+dp[f[f[x]]][2]); } }