poj3585 树形dp 二次扫描，换根法模板题

#include<iostream> #include<cstring> #include<cstdio> #include<vector> using namespace std; #define maxn 200005 struct Edge{ int to,next,c; }edge[maxn<<1]; int dp[maxn],f[maxn],vis[maxn],degree[maxn],head[maxn],tot; void addedge(int u,int v,int c){ edge[tot].to=v; edge[tot].c=c; edge[tot].next=head[u]; head[u]=tot; tot++; } void DP(int u){ vis[u]=1;dp[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]) continue; DP(v); if(degree[v]==1) dp[u]+=edge[i].c;//分两种情况，叶子节点和非叶子结点 else dp[u]+=min(edge[i].c,dp[v]); } } void dfs(int u){ vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(vis[v]) continue; if(degree[u]==1)//分两种情况 f[v]=dp[v]+edge[i].c;//u只有v一个子节点 else f[v]=dp[v]+min(edge[i].c,f[u]-min(dp[v],edge[i].c));//除了v外的其他节点 dfs(v); } } int main(){ int t,u,v,c,n; scanf("%d",&t); while(t--){ memset(head,-1,sizeof head); memset(degree,0,sizeof degree); tot=0; scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); addedge(v,u,c); degree[u]++,degree[v]++; } int root=1,ans=0; memset(vis,0,sizeof vis); DP(root); f[root]=dp[root]; memset(vis,0,sizeof vis); dfs(root); for(int i=1;i<=n;i++) ans=max(ans,f[i]); printf("%d\n",ans); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10224252.html