solution
经典的的方式。
转化一下题意就是:选一个根,使得所有叶子节点到该节点路径上最小边权之和最大。
先考虑的做法
用表示以1为根时i这棵子树内的答案。那么就有。
所以枚举一下根,然后每次这样dfs一遍,就可以在时间内解决问题了。
考虑优化该算法
我们只要在以1为根做一遍上面自下而上的dp之后,在做一遍自上而下的dp就可以转移出以任何一个点为根时的答案。
转移方程就是:,表示在自下而上的dp过程中,v对于u的贡献。
code
/* * @Author: wxyww * @Date: 2020-04-12 20:30:52 * @Last Modified time: 2020-04-12 20:43:48 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 200010; 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; } struct node { int v,nxt;ll w; }e[N << 1]; int head[N],ejs; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs; } ll f[N]; void dfs1(int u,int fa) { for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; dfs1(v,u); f[u] += min(e[i].w,f[v]); } if(!f[u]) f[u] = 1e14; } void dfs2(int u,int fa) { for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; f[v] += min(e[i].w,f[u] - min(f[v],e[i].w)); dfs2(v,u); } } int main() { int T = read(); while(T--) { int n = read(); memset(head,0,sizeof(head)); ejs = 0; for(int i = 1;i < n;++i) { int u = read(),v = read(),w = read(); add(u,v,w);add(v,u,w); } memset(f,0,sizeof(f)); dfs1(1,0); dfs2(1,0); ll ans = 0; for(int i = 1;i <= n;++i) { if(f[i] > 1e13) continue; ans = max(ans,f[i]); // printf("%lld ",f[i]); } // puts(""); cout<<ans<<endl; } return 0; }