【每日一题】 Accumulation Degree

思路：
一开始的想法就是直接每个点去dfs树形dp后取最大，复杂度n^2
看到数据范围后 想法直接见祖宗了 然后就去学了一下二次扫描和换根法。
简单介绍一下。
其实第一步就是上面说的dfs树形dp。
随便选取一个点为根，假设我们选1，则dp[root]表示以root为根的子树的最大流量。
对于root的子节点son
我们这样考虑，如果son的度为1，则dp[root] += e(root,son) 其中e(root,son)表示root到son这条河道的流量限制。
如果son的度不为1则dp[root] += min( dp[son],e(root,son) ) 什么意思呢 就是说我子树的流量可能允许很大，但是root到son这一条河道的允许通过量很小，对允许的量有了个限制，所以应该取最小值去加
这是第一次dfs 处理出来所有dp数组 表示以i为根节点的最大流量。

然后就是第二个dfs
用f[i]表示以i为源点的最大流量，那么刚才计算出来了dp[root]
f[root]显然等于dp[root]吧
第二个dfs主要是表示父节点root作为源点转移为子节点son作为源点快速计算出f[son]

那么son做为源点，流量有两个去处，一就是以son为子树的最大流量 也就是dp[son] 这个在第一个dfs里已经求过了
二就是root作为父节点时候除了给son的流量的剩余流量，对于root给除了son这个子树的流量的其他流量怎么算呢？
即f[root]-min(dp[son],e(root,son))这个就是root除去给son子树的流量的其他流量。
那么对于这些流量，他要从son流到其他地方，是不是只能经过son-root这条路 肯定是啊 我们把son和其子树作为一个整体节点看
整个图就剩下三个节点了 一个son 一个root 一个其他
那么son流到其他的流量就是min( e( root , son ) ,f[root] - min( dp[son] , e( root , son ) ) 从son到其他的地方去等价从其他地方到son来，我们已经知道了从其他的到root的流量，只要在跟从root->son这条河道允许的量比较一下即可。
所以对于root的度不为1，则有f[son] = dp[son] + min( e( root , son ) ,f[root] - min( dp[son] , e( root , son ) )
对于root的度为1，则f[son] = dp[son] + e( root , son )

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int dp[maxn],f[maxn];
bool vis[maxn];
int du[maxn];
struct node
{
    int to,cost;
};
vector<node> e[maxn];
void dfs1(int x){
    vis[x]=1;
    dp[x]=0;
    for(auto it:e[x]){
        int to=it.to,v=it.cost;
        if(vis[to]) continue;
        dfs1(to);
        if(du[to]==1) dp[x]+=v;
        else dp[x]+=min(dp[to],v);
    }
}
void dfs2(int x){
   vis[x]=1;
    for(auto it:e[x]){
        int to=it.to,v=it.cost;
        if(vis[to]) continue;
        if(du[x]==1) f[to]=dp[to]+v;
        else f[to]=dp[to]+min(f[x]-min(dp[to],v),v);
        dfs2(to);
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++) du[i]=vis[i]=0,e[i].clear();
        for(int i=1;i<n;i++){
            int x,y,d;cin>>x>>y>>d;
            du[x]++,du[y]++;;
            e[x].push_back({y,d});
            e[y].push_back({x,d});
        }
        dfs1(1);
        for(int i=1;i<=n;i++) vis[i]=0;
        f[1]=dp[1];
        dfs2(1);
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,f[i]);
        cout<<ans<<endl;
    }
    return 0;
}