直径数量问题

题目描述

给出一棵树，求树的直径及其数量（最长简单路径的长度和数量）。

输入格式

第一行一个整数 $n$ , $0\le n\le10^5$，
接下来有 $n-1$ 行，每行 $a,b$ 代表 $a$ 到第 $b$ 有一条长度为 $1$ 的边。
$1\le a,b\le n$

输出格式

输出两个数，分别表示树的直径和数量。

样例输入

5
5 1
1 2
2 3
2 4

样例输出

3 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 200005

//无根树转有根树
vector<ll> fa(MAXN), diam(MAXN), far(MAXN), cntd(MAXN), cntf(MAXN);
ll n, a, b;
deque<ll> v[MAXN];

void dfs(ll u, ll f) {
    cntf[u] = 1;
    for (auto &i : v[u]) {
        if (i != f) {
            dfs(i, u);
            if (far[i] + 1 == far[u]) {
                cntf[u] += cntf[i];
            }
            if (far[i] + 1 > far[u]) {
                far[u] = far[i] + 1;
                cntf[u] = cntf[i];
            }
        }
    }
    // 1
    diam[u] = far[u];
    cntd[u] = cntf[u];

/*
树的直径那个题三种情况计算的前后顺序会有影响吗

没影响，但是无论什么顺序都要考虑和其他情况直径一样时要把方案数加上去

大概就是
if 这种情况比上种情况直径更长 then
    更新直径为这种情况的直径，方案数为这种情况的方案数
else if 这种情况和之前情况算的直径一样 then
    方案数 += 这种情况的方案数
else 
    没有影响

*/
    //c3必须放这里，否则会wa
    for (auto &i : v[u]) {
        if (i != f) {
            if (diam[i] > diam[u]) {
                diam[u] = diam[i];
                cntd[u] = cntd[i];
            } else if (diam[i] == diam[u]) {
                cntd[u] += cntd[i];
            }
        }
    }

    // 2
    if (!((f != 0 || v[u].size() > 1) && (f == 0 || v[u].size() > 2))) {
        return;
    }
    ll m1 = 0, m2 = 0;
    for (auto &i : v[u]) {
        if (i != f) {
            if (far[i] + 1 > m2) {
                m2 = far[i] + 1;
            }
            if (m2 > m1) {
                swap(m1, m2);
            }
        }
    }
    // m1+m2
    ll cntn = 0;
    if (m1 == m2) {
        ll cnt = 0;
        for (auto &i : v[u]) {
            if (i != f && far[i] + 1 == m1) {
                cntn += cntf[i] * cnt;
                cnt += cntf[i];
            }
        }
    } else {
        ll cnt1 = 0, cnt2 = 0;
        for (auto &i : v[u]) {
            if (i != f) {
                if (far[i] + 1 == m1) {
                    cnt1 += cntf[i];
                }
                if (far[i] + 1 == m2) {
                    cnt2 += cntf[i];
                }
            }
        }
        cntn = cnt1 * cnt2;
    }
    if (m1 + m2 > diam[u]) {
        diam[u] = m1 + m2;
        cntd[u] = cntn;
    } else if (m1 + m2 == diam[u]) {
        cntd[u] += cntn;
    }
    // 3
}

int main() {
    cin >> n;
    while (--n) {
        cin >> a >> b;
        v[a].emplace_back(b);
        v[b].emplace_back(a);
    }
    dfs(1, 0);  //无根树转有根树,假定以1为根节点
    cout << diam[1] << " " << cntd[1];
    return 0;
}