每日一题4月13日Accumulation Degree+201400 树学 树形dp

原谅我前面一题每日一题没做。
数学啊数学，太难了啊。。

来看这里的每日一题，看到题目以为是网络流，直接点开了题解。发现推荐做201400树学。
好的，那么先来看树学。
链接：https://ac.nowcoder.com/acm/problem/201400
题目大意：
给一棵树，可以找一个点作为根，然后计算出深度和。问如果选根让深度和最小，求这个最小值。
数据范围n<=1e6

思路：
这个数据量肯定是考虑线性复杂度了。
显然，如果指定一个点作为根，我们是可以在O(n)时间上计算出∑dep[i]。
如果在这个基础上枚举根，就要再乘一个n，显然不可接受。
那能不能在枚举根的时候，O（1）的计算出答案呢？让我们考虑根转移的时候的情况：
假设从u->v，如果我们已经计算出了f[u]表示以u为根的答案。
显然u和u上方的节点dep+1,v和v下方的节点dep-1，那么我们可以得到转移方程：
f[v]=f[u]+u及u上方的节点数量-v及v下方的节点数量
这里我们可以先跑一边dfs,用son[x]表示x的子树节点数量（包括x）。
因此我们在重新写一遍转移方程为：
f[v]=f[u]+(n-son[v])-son[v]
两次dfs就好了。
复杂度O(n)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,son[1000050],dep[1000050];
long long ans,f[1000050];
vector<int>vt[1000040];
int dfs(int x,int fa){
    son[x]=1;
    for(int i=0;i<vt[x].size();i++){
        int y=vt[x][i];
        if(y==fa)continue;
        dep[y]=dep[x]+1;
        son[x]+=dfs(y,x);
    }
    ans+=dep[x];
    return son[x];
}
int minw=0x3f3f3f3f;
void dfs2(int x,int fa){
    for(int i=0;i<vt[x].size();i++){
        int y=vt[x][i];
        if(y==fa)continue;
        f[y]=f[x]+n-son[y]-son[y];
        dfs2(y,x);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(1,-1);
    f[1]=ans;
    dfs2(1,-1);
    for(int i=2;i<=n;i++)ans=min(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}

再来看这道题目：
题目大意：
给一棵树，每条边上有一个容量，从某个点出发一直到叶子节点，可以计算出最大的容量。这里的容量不能超过路劲上任意一条边的容量。令A（x）表示从点x出发到所有它子树的叶子的容量和的最大值。

思路：
有了上一题，我们可以参考刚刚的思路。
首先定一个根节点1，我们可以计算出A[1]的值。
这里我们可以用一个dfs来解决，A[1]=∑min(w(1,v),A[v])
注意，这么计算的A[x]同上题是一样的，即A[x]只能表示从x出发向下的容量和，x上方的我们没有计算到。
显然一遍dfs以后，我们预处理出了A[x]，并且只有A[1]是包括所有子树的答案。

接着我们考虑u->v的转移了：
显然从u到v，现在变成了以v为中心去计算，考虑v的上方，显然我们有
A[u]-min(w(u,v),A[v])
注意：由于v是从u转移过来的，此时的A[u]已经是包括了所有子树的答案
然后是v的下方，就是A[v]
那么我们有：
A[v]=min(w(u,v),A[u]-min(w(u,v),A[v]) )+A[v]
注意到叶子节点的时候要特殊处理一下，因为叶子节点下方没有东西了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,d[200050];
long long A[200040],ans;
struct node{
    int to,w,next;
}p[400050];
int tot,head[200050];
void init()
{
    tot=0;
    for(int i=0;i<400050;i++)p[i].next=-1;
    memset(head,-1,sizeof(head));
    memset(A,0,sizeof(A));
    memset(d,0,sizeof(d));
}
void add(int a,int b,int c){
    tot++;
    p[tot].to=b;
    p[tot].w=c;
    p[tot].next=head[a];
    head[a]=tot;
}
long long dfs(int x,int fa){
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(y==fa)continue;
        if(d[y]==1)A[x]+=p[i].w;    //叶子节点的特殊处理，下方直接设置为流量边
        else A[x]+=min(1ll*p[i].w,dfs(y,x));
    }
    return A[x];
}
void dfs2(int x,int fa){
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(y==fa)continue;
        if(d[y]==1)A[y]=min(1ll*p[i].w,A[x]-1ll*p[i].w);  //叶子点处理
        else
        A[y]=min(1ll*p[i].w,A[x]-min(1ll*p[i].w,A[y]))+A[y];
        dfs2(y,x);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        init();
        int n;
        cin>>n;
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
            d[x]++;
            d[y]++;
        }
        dfs(1,-1);
        ans=A[1];
      //  cout<<ans<<endl;
        dfs2(1,-1);
        for(int i=1;i<=n;i++)ans=max(ans,A[i]);
        cout<<ans<<endl;
    }
    return 0;
}