题目链接
思路
用(f[i])表示完成第(i)棵子树所需要得时间。
考虑如果有两个子树(a)和(b),如果先去完成子树(a),那么对于花费得时间就是(f[b] + siz[a] times 2 + 1)
所以如果有先遍历(a)更优秀的话。那么一定有(f[b] + siz[a] times 2 + 1 le f[a] + siz[b] times 2+ 1)
即(f[a] – siz[a] times 2 le f[b] – siz[b] times 2)
所以对于当前节点的每个子树按照上面的方法排个序。然后统计一下答案即可。
有个坑点就是必须最后完成(1)号节点,所以最后不能直接输出(f[1]),好在从样例里可以发现(233)
代码
/* * @author: wxyww * @date: 2019-02-13 07:26:04 * @last modified time: 2019-02-13 09:13:20 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 500000 + 100; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } vector<int>e[n]; int f[n],siz[n]; int n,c[n]; bool cmp(int x,int y) { return f[x] - siz[x] * 2 > f[y] - siz[y] * 2; } void dfs(int u,int father) { int k = e[u].size(); siz[u] = 1; int now = 0; if(c[u] != 1) f[u] = c[u]; for(int i = 0;i < k;++i) { int v = e[u][i]; if(v == father) continue; dfs(v,u); siz[u] += siz[v]; } sort(e[u].begin(),e[u].end(),cmp); for(int i = 0;i < k;++i) { int v = e[u][i]; if(v == father) continue; f[u] = max(f[u],now * 2 + f[v] + 1); now += siz[v]; } } int main() { n = read(); for(int i = 1;i <= n;++i) c[i] = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(); e[u].push_back(v);e[v].push_back(u); } dfs(1,0); printf("%dn",max(f[1],(n - 1) * 2 + c[1])); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605224.html