昨晚上学了二次扫描后，才发现省赛的树形dp题竟然可以用这个写。

我们用f[u] 表示：以节点u为根的递增路径条数。并且计算这些路径相互之间的贡献。

void dfs1(int u, int fa){

    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to==fa){
            continue;
        }

        dfs1(to, u);
        if(u>to){
            s[u]+=f[u]*(f[to]+1);
            f[u]+=(f[to]+1);
        }
    }
}

为什么计算的时候是
s[u]+=f[u]*(f[to]+1);
f[u]+=(f[to]+1);
我们证明一下：

同理二次扫描一样。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
vector<int> v[200005];
LL s[200005];
LL f[200005];
void dfs1(int u, int fa){

    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to==fa){
            continue;
        }

        dfs1(to, u);
        if(u>to){
            s[u]+=f[u]*(f[to]+1);
            f[u]+=(f[to]+1);
        }
    }
}

void dfs2(int u, int fa){

    if(u>fa){
        s[u]+=f[u]*(f[fa]+1);
        f[u]+=(f[fa]+1);
    }
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs2(to, u);
        }
    }
}

int main()
{
    //freopen("e1.in", "r", stdin);
    int t;scanf("%d", &t);
    while(t--){
        memset(s, 0, sizeof(s));
        memset(f, 0, sizeof(f));
        int n, u, to;
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            v[i].clear();
        }
        for(int i=1; i<=n-1; i++){
            scanf("%d%d", &u, &to);
            v[u].push_back(to);
            v[to].push_back(u);
        }
        dfs1(1, 0);
        dfs2(1, 1<<30);
        LL ans=0;
        for(int i=1; i<=n; i++){
            ans+=s[i];
        }
        printf("%lld\n", ans*2);
    }

    return 0;
}