【原题题面】

【题解大意】

乍一看感觉以为网络流表示一点都不会不会不会。

然后发现可以树形dp搞一下。

再然后知道了换根dp。

设d[x]表示以x为根的子树中把x做为源点，从x出发流向子树的流量最大是多少。

d[x] += min(d[y],z);(deg[y]!=1)

d[x] = z; (deg[y]==1)

f[x]表示以x做为源点，从x出发流向整个水系的流量最大是多少。

f[y] = d[y] + min(f[x] - min(d[y],z));(deg[x]!=1)

f[y] = d[y] + z;

【code】

暴力：

#include
      
       using namespace std;#define File "degree"#define ll long longinline void file(){    freopen(File".in","r",stdin);    freopen(File".out","w",stdout);}inline int read(){    int x = 0,f = 1; char ch = getchar();    while(ch < '0'||ch > '9'){
    if(ch == '-')f = -1; ch = getchar();}    while(ch >= '0' && ch <= '9'){x = (x<<1) + (x<<3) + ch-'0'; ch = getchar();}    return x * f;}const int mxn = 2e5+3;int n;struct edge{    int nxt,y,v;}e[mxn<<1];int to[mxn],len;inline void add(int xx,int yy,int vv){    e[++len].nxt = to[xx];    to[xx] = len;    e[len].y = yy;    e[len].v = vv;}bool v[mxn];int d[mxn],deg[mxn];inline void dp(int x){    v[x] = 1;    d[x] = 0;    for(int i = to[x]; i;i = e[i].nxt){        int y = e[i].y,z = e[i].v;        if(v[y]) continue;        dp(y);        if(deg[y]==1) d[x] += z;        else d[x] += min(d[y],z);    }}int T;int main(){//    file();    T = read();    while(T--){        n = read();        len = 1;        memset(v,0,sizeof v);        memset(d,0,sizeof d);        memset(to,0,sizeof to);        memset(deg,0,sizeof deg);        for(int i = 1;i < n; ++i){            int x = read(),y = read(),z = read();            add(x,y,z),add(y,x,z);            deg[x]++,deg[y]++;         }        int ans(0);        for(int i = 1;i <= n; ++i){            memset(d,0,sizeof d);            memset(v,0,sizeof v);             dp(i);            ans = max(ans,d[i]);        }        printf("%d\n",ans);     }     return 0;}
      

标程：

#include
      
       using namespace std;#define File "degree"#define ll long longinline void file(){    freopen(File".in","r",stdin);    freopen(File".out","w",stdout);}inline int read(){    int x = 0,f = 1; char ch = getchar();    while(ch < '0'||ch > '9'){
    if(ch == '-')f = -1; ch = getchar();}    while(ch >= '0' && ch <= '9'){x = (x<<1) + (x<<3) + ch-'0'; ch = getchar();}    return x * f;}const int mxn = 2e5+3;int T,n;struct edge{    int nxt,y,v;}e[mxn<<1];int to[mxn],len;inline void add(int xx,int yy,int vv){    e[++len].nxt = to[xx];    to[xx] = len;    e[len].y = yy;    e[len].v = vv;}/*151 2 111 4 133 4 54 5 10*/bool v[mxn];int d[mxn],deg[mxn],f[mxn];inline void dp(int x){    v[x] = 1;    d[x] = 0;    for(int i = to[x]; i;i = e[i].nxt){        int y = e[i].y,z = e[i].v;        if(v[y]) continue;        dp(y);        if(deg[y]==1) d[x] += z;        else d[x] += min(d[y],z);    }}inline void dfs(int x){    v[x] = 1;    for(int i = to[x]; i;i = e[i].nxt){        int y = e[i].y,z = e[i].v;        if(v[y]) continue;        if(deg[x]==1) f[y] = d[y] + z;        else f[y] = d[y] + min(f[x] - min(d[y],z),z);        dfs(y);    }}int main(){//    file();    T = read();    while(T--){         n = read();        len = 1;        memset(v,0,sizeof v);        memset(f,0,sizeof f);        memset(d,0,sizeof d);        memset(deg,0,sizeof deg);        memset(to,0,sizeof to);        for(int i = 1;i < n; ++i){            int x = read(),y = read(),z = read();            add(x,y,z),add(y,x,z);            deg[x]++,deg[y]++;        }        int rt(1);        dp(rt);        memset(v,0,sizeof v);        f[rt] = d[rt];        dfs(rt);        int ans(0);        for(int i = 1;i <= n; ++i) ans = max(ans,f[i]);        printf("%d\n",ans);    }     return 0;}