hdu6686 Rikka with Travels(树的直径)

题目链接
大意：给你一棵树，让你求出多少对 $(l,r)$(l,r)，使得存在两条长度为 $l,r$l,r的链且他们不相交

思路:我们直接枚举边，每条边将一棵树分成两颗，求出两棵树的分别直径即可。
具体操作是：
先以1为根，记录每个节点的最长向下延申长度x，和子树内前三大的x,然后就可以计算出过当前节点的最长链了，
每个节点记录子树内前三大的最长链。
然后就直接换根统计答案即可，把旧根的贡献给新根，更新新根的信息，注意一点就是旧根的最长链(不包含新根)也要传递给新根。剩下就没什么坑了

#include<bits/stdc++.h>

#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e5 + 11;
int t, n, f[N];
vector<int>v[N];
struct uzi {
    int fi, se;
} Q[N][5], P[N][5];
int q[N];
void dfs(int now, int pre) {
    f[now] = 1;
    //统计每个节点向下延申的最长距离
    //该节点前2大的加起来就是以该节点为根时候的直径
    for (int k : v[now]) {
        if (k == pre)continue;
        dfs(k, now);
        f[now] = max(f[now], f[k] + 1);
        if (f[k] >= Q[now][1].fi) {
            Q[now][3] = Q[now][2];
            Q[now][2] = Q[now][1];
            Q[now][1] = {f[k], k};
        } else if (f[k] >= Q[now][2].fi) {
            Q[now][3] = Q[now][2];
            Q[now][2] = {f[k], k};
        } else if (f[k] >= Q[now][3].fi) {
            Q[now][3] = {f[k], k};
        }
        if (q[k] > P[now][1].fi) {
            P[now][3] = P[now][2];
            P[now][2] = P[now][1];

            P[now][1] = {q[k], k};

        } else if (q[k] > P[now][2].fi) {
            P[now][3] = P[now][2];

            P[now][2] = {q[k], k};

        } else if (q[k] > P[now][3].fi) {

            P[now][3] = {q[k], k};
        }
    }
    q[now] = Q[now][1].fi + Q[now][2].fi + 1;
    return ;
}
LL G[N << 2];
void bfs(int now, int pre) {
    for (auto k : v[now]) {
        if (k == pre)continue;
        int NEED = 0;
        int res = 0;
        for (int j = 1; NEED < 2 && j <= 3; j++) {
            if (Q[now][j].se != k) {
                res += Q[now][j].fi;
                NEED++;
            }
        }
        res++;
        int nwa = res;
        for (int j = 1; j <= 3; j++) {
            if (P[now][j].se != k) {
                res = max(res, P[now][j].fi);
            }
        }
        NEED = 0;
        int bes = 0;
        for (int j = 1;  j <= 2; j++)bes += Q[k][j].fi;
        bes++;
        for (int j = 1; j <= 3; j++)bes = max(bes, P[k][j].fi);
        G[bes] = max(1ll * res, G[bes]);
        G[res] = max(1ll * bes, G[res]);
        //从旧根中找一个不是新根的节点且这个节点向下延申长度最长，设长度为x
        //那么旧根就可以做为新根的 一个节点 且延伸长度为x+1


        for (int i = 1; i <= 3; i++) {
            if (Q[now][i].se != k) {
                f[k] = Q[now][i].fi + 1;
                if (f[k] >= Q[k][1].fi) {
                    Q[k][3] = Q[k][2];
                    Q[k][2] = Q[k][1];
                    Q[k][1] = {f[k], now};
                } else if (f[k] >= Q[k][2].fi) {
                    Q[k][3] = Q[k][2];
                    Q[k][2] = {f[k], now};
                } else if (f[k] >= Q[k][3].fi) {
                    Q[k][3] = {f[k], now};
                }
                break;
            }

        }
        for (int i = 1; i <= 3; i++) {
            if (P[now][i].se != k) {
                int K = P[now][i].fi;
                if (K > P[k][1].fi) {
                    P[k][3] = P[k][2];
                    P[k][2] = P[k][1];
                    P[k][1] = {K, now};
                } else if (q[k] > P[k][2].fi) {
                    P[k][3] = P[k][2];
                    P[k][2] = {K, now};
                } else if (q[k] > P[k][3].fi) {
                    P[k][3] = {K, now};
                }
            }
        }
        if (f[k] >= P[k][1].fi) {
            P[k][3] = P[k][2];
            P[k][2] = P[k][1];
            P[k][1] = {f[k], now};
        } else if (f[k] >= P[k][2].fi) {
            P[k][3] = P[k][2];
            P[k][2] = {f[k], now};
        } else if (f[k] >= P[k][3].fi) {
            P[k][3] = {f[k], now};
        }
        if (nwa >= P[k][1].fi) {
            P[k][3] = P[k][2];
            P[k][2] = P[k][1];
            P[k][1] = {nwa, now};
        } else if (nwa >= P[k][2].fi) {
            P[k][3] = P[k][2];
            P[k][2] = {nwa, now};
        } else if (nwa >= P[k][3].fi) {
            P[k][3] = {nwa, now};
        }
        bfs(k, now);
    }
    return;
}
LL ASN[N];
int main() {
    //freopen("in", "r", stdin);
    for (scanf("%d", &t); t; t--) {
        scanf("%d", &n);
        G[n + 1] = G[n] = 0;
        for (int i = 1; i <= n; i++) {
            v[i].clear();
            f[i] = 0;
            G[i] = 0;
            q[i] = 0;
            for (int j = 1; j <= 3; j++)Q[i][j].fi = Q[i][j].se = 0, P[i][j].fi = P[i][j].se = 0;
        }
        for (int i = 1; i < n; i++) {
            int s, T;
            scanf("%d %d", &s, &T);
            v[s].pb(T);
            v[T].pb(s);
        }
        //if (t == 4)continue;
        dfs(1, 0);
        bfs(1, 0);
        LL ANS = 0;
        for (int i = n - 1; i >= 1; i--) {
            G[i] = max(G[i], G[i + 1]);
            ANS += G[i];
        }
        printf("%lld\n", ANS );
    }
    return 0;
}