建设公司和建筑公司有什么区别,关键词优化seo排名,好的免费移动网站建设平台有哪些,如何改变wordpress文本的字体颜色文章目录题目描述题解#xff1a;传送时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format:%lld 题目描述 小H正在玩一个战略类游戏#xff0c;她可以操纵己方的飞机对敌国的N座城市(编号为1~N…
文章目录题目描述题解传送时间限制C/C 2秒其他语言4秒 空间限制C/C 262144K其他语言524288K 64bit IO Format:%lld 题目描述 小H正在玩一个战略类游戏她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸
敌国的城市形成了一棵树小H会依次进行Q次轰炸每次会选择一个城市A进行轰炸和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数)轰炸结束后小H还想知道当前城市A受损的次数
作为游戏的开发者之一你有义务回答小H的问题 输入描述: 第1行两个整数N(1≤N≤750000)、Q(1≤Q≤750000) 第2~N行每行两个整数表示树上的一条边 第N1~NQ行每行一个整数表示小H这次轰炸的城市 输出描述: 输出Q行每行一个整数表示这一次轰炸的城市在此次轰炸后共计受损几次 示例1 输入
4 4
1 2
2 3
3 4
1
2
3
4输出
1
2
3
3题解
我一开始以为一个城市被轰炸后还在。。。发现并不是 我们来分析一个点被轰炸哪些点会受到牵连 图中点1被轰炸1的父亲的父亲儿子的儿子还有兄弟父亲的儿子这些点会受损同理这些点被轰炸1也会被受损。
fa[]表示父子关系 我们可以用二维数组表示dp[i][j]来表示i节点攻击范围 j 1 为结点i被轰炸的次数 j 2 结点i的子结点被轰炸的次数 j 3 结点i的子结点的子结点被轰炸的次数 而每个节点的父亲节点只有一个我们可以用fa[x]来实现而儿子节点可以有多个我们通过二维数组来实现。
总结图中节点x被轰炸的情况; 1.本身被轰炸 dp[x][1] 2.子节点被轰炸 dp[x][2] 3.子节点的子节点被轰炸 dp[x][3] 4.父亲节点被轰炸 dp[fa[x]][1] 5.父亲的父亲节点被轰炸 dp [ fa [ fa [ x ] ] ] [ 1 ] 6.兄弟节点被轰炸 dp[fa [ x ] ] [ 2 ] - dp [x ] 1
维护好这些这样我们就可轻松进行查询 当x被轰炸时,就让上面6种情况,注意第六种情况和第一种情况可以合并所以这两个合成一个 dp[fa [ x ] ] [ 2 ]就行。 最后输出距离x距离为01,2的点 距离为0即本身 dp[x][1] 距离为1 dp[fa[x]][2] 距离为2 dp [ fa [ fa [ x ] ] ] [ 3 ] 加起来就是x的答案
#includebits/stdc.h
#includevector
using namespace std;
const int maxn750003;
int n,q,fa[maxn],dp[maxn][4];
vectorint edge[maxn];
void dfs(int u,int f){fa[u]f;for(int v:edge[u])if(v!f)dfs(v,u);}
int main(){scanf(%d%d,n,q);int u,v,x;for(int i1;in;i){scanf(%d%d,u,v);edge[u].push_back(v);edge[v].push_back(u);}dfs(1,0);while(q--){scanf(%d,x);dp[fa[x]][2];//父亲的儿子情况1和6dp[fa[x]][1];//父亲本身 情况4dp [ fa [ fa [ x ] ] ] [ 1 ] ;//父亲的父亲 情况5dp [ x ] [ 2 ] ;//儿子 情况2dp [ x ] [ 3 ] ;//儿子的儿子 情况3printf(%d\n,dp[x][1]dp[fa[x]][2]dp[fa[fa[x]]][3]);}
}
