这题不简单啊

题面

小Q最近学习了一些图论知识。

根据课本，有如下定义。

树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。

如果一棵树有N个节点，可以证明其有且仅有N-1 条边。

路径：一棵树上，任意两个节点之间最多有一条简单路径。

我们用 dis(a,b)表示点a和点b的路径上各边长度之和。

称dis(a,b)为a、b两个节点间的距离。

直径：一棵树上，最长的路径为树的直径。

树的直径可能不是唯一的。

现在小Q想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

输入格式

第一行包含一个整数N，表示节点数。

接下来N-1行，每行三个整数a, b, c ，表示点a和点b之间有一条长度为c的无向边。

输出格式

共两行。

第一行一个整数，表示直径的长度。

第二行一个整数，表示被所有直径经过的边的数量。

数据范围

2≤N≤200000,点的编号从1开始。
c≤109

输入样例：

6 
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

输出样例：

1110
2

题解

直径的相同路径必定连续, 好好画图思考一下(两次bfs,是怎么求出来直径的)

所以我们首先求出来一条直径, 如果还存在另一条直径

那么必定是, 再求出直径的某个点处走出一条分支, 且这条分支的长度和原来分支长度相等

所以所求就是 上分叉, 一条直线, 下分叉 中直线包含有多少条路径

就是在原直径p, q两个端点, 正和倒着求出 直径上两个端点 中间的路径唯一无分叉

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

const int N = 200005;

int n, m, _, k;
int h[N], ne[N << 1], co[N << 1], to[N << 1], tot;
int f[N], b[N], dep[N], p, q, r, l;
ll d[N], fd[N];
unordered_set<int> st;

void add(int u, int v, int c) { to[++tot] = v; ne[h[u] = tot] = h[u]; co[tot] = c; }

void dfs(int u, int fa) {
    for (int i = h[u], y = to[i]; i; y = to[i = ne[i]]) if (y != fa) {
        f[y] = u; b[y] = i; dep[y] = dep[u] + 1; d[y] = d[u] + co[i];
        if (d[0] < d[y]) d[0] = d[y], f[0] = y; dfs(y, u);
    }
}

ll work(int& p, int& q) {
    d[0] = -1; dep[1] = d[1] = 0; dfs(1, 0); p = f[0];
    d[0] = -1; dep[p] = d[p] = 0; dfs(p, 0); q = f[0];
    return d[q];
}

void dfss(int u, int fa) {
    for (int i = h[u], y = to[i]; i; y = to[i = ne[i]]) if (y != fa) {
        dfss(y, u);
        fd[u] = max(fd[u], fd[y] + co[i]);
        if (!st.count(u) || st.count(y)) continue;
        if (d[q] - d[u] == fd[y] + co[i] && dep[r] > dep[u]) r = u;
        if (d[u] == fd[y] + co[i] && dep[l] < dep[u]) l = u;
    }
}

int main() {
    IOS; cin >> n;
    rep(i, 2, n) {
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c); add(v, u, c);
    }
    cout << work(p, q) << '\n';
    st.insert(p);
    for (int i = q; i != p; st.insert(i), i = f[i]);
    r = q, l = p; dfss(p, 0);
    cout << max(0, dep[r] - dep[l]);
    return 0;
}