在安庆哪里可以做公司网站,ui设计培训费一般多少,广东富盈建设有限公司企业网站,最新新闻热点事件摘抄300字正题
题目链接:http://poj.org/problem?id3585 题目大意
有棵无根树#xff0c;当你选择一个点为根时#xff0c;价值就是根节点到所有叶节点的路上的最小权值之和。 解题思路
我们可以先计算一次点1为根时的答案#xff0c;路上统计答案为didi#xff0c;然后定义fifi…正题
题目链接:http://poj.org/problem?id3585 题目大意
有棵无根树当你选择一个点为根时价值就是根节点到所有叶节点的路上的最小权值之和。 解题思路
我们可以先计算一次点1为根时的答案路上统计答案为didid_i然后定义fifif_i为以i为根节点时的权值。 然后我们再由f1f1f_1转移到后面。我们考虑每一个子节点 首先我们知道这个父节点转移后价值是dxdxd_x然后原来的这个子节点的子树和其他的点都要和wiwiw_i产生影响具体转移
fydymin{fx−min{dy,wi},wi}fydymin{fx−min{dy,wi},wi}f_y=d_y+min\{f_x-min\{d_y,w_i\},w_i\} code
#includecstdio
#includecstring
#includealgorithm
#define N 200010
using namespace std;
struct tree{int to,next,w;
}a[2*N];
int n,in[N],w,ls[N],f[N],d[N],tot,rx,ry,ans,t;
bool v[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;in[y];
}
void dp(int x)//第一次计算
{v[x]1;for(int ils[x];i!-1;ia[i].next){int ya[i].to;if(v[y]) continue;dp(y);if(in[y]1) d[x]a[i].w;else d[x]min(d[y],a[i].w);}
}
void dfs(int x){v[x]1;for(int ils[x];i!-1;ia[i].next){int ya[i].to;if(v[y]) continue;if(in[x]1) f[y]d[y]a[i].w;else f[y]d[y]min(f[x]-min(d[y],a[i].w),a[i].w);dfs(y);}
}//换根
int main()
{scanf(%d,t);while(t--){tot0;memset(ls,-1,sizeof(ls));memset(f,0,sizeof(f));memset(d,0,sizeof(d));memset(v,0,sizeof(v));memset(in,0,sizeof(in));scanf(%d,n);for (int i1;in;i){scanf(%d%d%d,rx,ry,w);addl(rx,ry,w);addl(ry,rx,w);//连边}dp(1);f[1]d[1];ans0;memset(v,0,sizeof(v));dfs(1);for(int i1;in;i)ansmax(ans,f[i]);printf(%d\n,ans);}
}
