题意
给出一个有n个节点的有根树,1 为根节点,根节点有无穷多个兵,每一秒可以让任意一个兵向任意一个地方移动一步,兵所到的点被占领,问最少需要经过多少秒,才能将所有的点都占领
思路
暴力走一遍,然后每次判断,
- 是从根节点更新距离短
- 还是从最近的节点更新距离短。
最近的点可能是:父亲节点(第一次到达该点)也可能是子节点(从子节点遍历回来)。
然后对于一个子树,应该最后走最深的链
因为
-
如果相邻的子树从根节点走下来士兵
最深的链只走一次,其余的链都会走两次。长度最短。 -
如果相邻的子树还是该树的士兵遍历
所有的链都会走两次。长度最短。
因此,为了最后走最长链;对于每个子树,按照 最长链 进行排序,
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1e6+10;
const int inf = 1e9+7;
int n;
vector<pii> tree[N];//单向边
int dep[N];//深度
int cnt[N];//距离
int ans;
//找子树最长链,并排序
int dfs1(int u,int d){
if(tree[u].empty()) return 1;
dep[u]=d;
for(pii &x: tree[u])
x.first=max(x.first,dfs1(x.second,d+1));
sort(tree[u].begin(),tree[u].end());
return tree[u].back().first+1;
}
//找到最小花费
int dfs2(int u,int dis){
cnt[u]=dis;
if(tree[u].empty()) return 1;
int minn=dis;
for(pii it: tree[u])
minn=min(dep[u],dfs2(it.second,minn+1));//维护距离与深度的最小值
return minn+1;
}
void init(){
for(int i =0;i<=n;i++)
tree[i].clear();
ans=0;
}
void solve() {
init();
cin >> n;
int x;
for (int i = 2; i <= n; i++) {
cin >> x;
tree[x].push_back({ 0,i });//深度,编号
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++)
//当前点为叶子节点,更新答案
if (tree[i].empty())
ans += cnt[i];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin >> t;
for (int i = 1; i <= t; i++) {
solve();
cout << "Case #" << i << ": " << ans << endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/kingwz/p/16795738.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性