Accumulation Degree

题意：
不知道题目讲什么真的要命，水从根结点往下流，流量不能超过边的权值,sum[i]表示i结点最多可以流出多少水（流量），这个需要从叶子节点一直回溯来求，父结点的流量sum[u]+=min(w,sum[v]),w表示u和v边的权值，特别的当v是叶子结点的时候，sum[v]=0,sum[u]+=w。
知道了换根dp的模板后难的就是不理解题意

思路：

如果对每一个结点都dfs一次复杂度为O(n^2)，显然是不可以的，所以要用到换根dp。
前要是：每个结点的流量sum[]初始化为0，每个结点最后一次出现的位置head[]也初始化为0。
用链式前向星存储所有结点，然后以1为根建立一棵树，求全部子树的根流量，其中sum[1]就是根为1时整棵树的流量。
如果这个结点是叶子结点，不做处理，sum[v]=0,sum[u]+=w，
如果sum[v]!=0,sum[u]+=min(w,sum[v])。这个过程开一个dfs然后回溯就可以。
接下来换根，其实不需要分类讨论。
根节点为u，子节点为v，将v换为根，此时u为子树的根，它的值为原来做根时的流量sum[u]减去v对它的贡献min(w,sum[v]),这时v作为根的流量只要在原来的基础上加上流到u这棵子树的流量就是v此时的根流量：sum[v]+min(sum[u]-min(w,sum[v]),w)。注：这个表达式的sum[u]表示的是u为根时的值，为了方便表述才这么写，sum[v]还是原来的意思，具体还是看代码。
换根的话，我觉得和其它结点没什么区别，但是别的大佬喜欢特判然后令它的值为边的权值，感觉有点问题----这和以叶子节点为根得到的根流量的值不一样了，但是因为叶子结点为根的流量一定不是最大的，对结果是没有影响的。

特别要小心：数组开多了最好设个宏常量什么的，我刚刚写的树学，回来写这个结果有一个数组多删了一个0，wa了几个小时无果，最好还是刘大佬看出来了。这是多组输入比树学要多个初始化，因为这个wa了几次。写完树学再写这个记得把数组开小点,还就是dfs的顺序不要错。接下来套模板就没问题了,O(n)的复杂度能过！

Code:

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int node[400005],Next[400005],head[200005],dis[400005],tot;
void add(int x,int y,int c) {
    node[++tot]=y;
    dis[tot]=c;
    Next[tot]=head[x];
    head[x]=tot;
}
int sum[200005];
void dfs1(int x,int f) {
    sum[x]=0;
    for(int i=head[x];i;i=Next[i]) {
        int y=node[i];
        if(y==f)    continue;
        dfs1(y,x);
        if(!sum[y])    sum[x]+=dis[i];
        else sum[x]+=min(dis[i],sum[y]);
    }
}
int ans,n;
void dfs2(int x,int f,int val) {
    ans=max(ans,val);
    for(int i=head[x];i;i=Next[i]) {
        int y=node[i];
        if(y == f) continue;
        dfs2(y,x,sum[y]+min(val-min(dis[i],sum[y]),dis[i]));
    }
}
int main() {
    js;
    int t; cin>>t;
    while(t--) {
        cin>>n;    ans=tot=0;
        for(int i=1;i<=n;++i)    head[i]=0;
        for(int i=2;i<=n;++i) {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }
        dfs1(1,0);
        dfs2(1,0,sum[1]);
        cout<<ans<<endl;
    }
    return 0;
}

Tree

题意：
给你一颗有n个节点的树，你需要找出一个点作为root，使得图片说明 的值最小。
其中deep[i]表示root为根时结点i的深度。

思路：

链式向前星存储全部结点，然后以1为根dfs建立一棵树，sum[i]表示结点i为根的子树的深度和，计算出sum[1]，回溯就可以了，在统计每个结点的深度。
最后再开一个dfs换根，根结点u和儿子v替换，v的子树全部的深度减1，树u上除了v的子树上的结点深度全部加一，则v此时的深度为sum[u]+(n-size[v])-size[v]。注：这个表达式的sum[u]表示的是u为根时的值，为了方便表述才这么写，具体还是看代码。

Code:

代码戳我