题面

题目链接

大秦 为你打开 题目传送门

备用题面

给一棵 $n$ 个节点的树, 节点编号为 $1$ ~ $n$ ，每条边有权值。

对于一棵树，最长的路径为树的直径，可能不唯一。

求该树的直径长度是多少，以及有多少条边满足所有的直径都经过该边。

思路

首先直径肯定都会算，我们记录一个答案，把直径的一个端点作为根建树，然后对于每一个点记录一下该节点的子树中到根节点最远的是多远，顺便记录一下一共有几个，如果当前点是直径上的点的话我们先判断一下是否存在两个及以上最长路径，如果是的话答案缩小到深度减一，如果存在子树中到根节点的距离的最大值等于根节点到该点的距离，我们直接将答案减去深度减一直接输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    char buf[1 << 20], *p1, *p2;
    #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
    inline void read(char *s) {
        scanf("%s", s + 1);
    }
};
using namespace FastIO;

const int N = 2e5 + 10;

struct Edge {
    int to, nt, wt;
    Edge() {}
    Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[N << 1];
int hd[N], cnte;
inline void AddEdge(int u, int v, int w) { 
    e[++cnte] = Edge(v, hd[u], w);
    hd[u] = cnte;
}

int n;

inline void Input() {
    read(n);
    int u, v, w;
    for(int i = 1; i < n; i++) {
        read(u, v, w);
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
}

int fa[N], dep[N];
ll dis[N];
int ans;

int vis[N];
ll ma[N];

inline void Dfs1(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    for(int i = hd[u]; i ; i = e[i].nt) {
        int v = e[i].to;
        if(v == f) continue;
        dis[v] = dis[u] + e[i].wt;
        Dfs1(v, u);
    }
}

inline void Dfs2(int u) {
    ll mx = -1;
    int js = 0, js2 = 0;
    for(int i = hd[u]; i ; i = e[i].nt) {
        int v = e[i].to;
        if(v == fa[u])continue;
        Dfs2(v);
        if(ma[v] >= mx) {
            if(ma[v] > mx) {
                mx = ma[v];
                js = 1;
            }
            else js++;
        }
        if(ma[v] - dis[u] == dis[u]) {
            js2++;
        }
    }
    if(vis[u]) {
        if(js2) {
            ans -= dep[u] - 1;
            printf("%d\n", max(ans, 0));
            return exit(0);
        }
        else if(js > 1) {
            ans = dep[u] - 1;
        }
    }
    mx = max(mx, dis[u]);
    ma[u]=mx;
}

inline void Work() {
    Dfs1(1, 0);
    memset(fa, 0, sizeof(fa));
    int du = 0, dv = 0;
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[du]) {
            du = i;
        }
    }
    memset(dis, 0, sizeof(dis));
    Dfs1(du, 0);
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[dv]) {
            dv=i;
        }
    }
    printf("%lld\n", dis[dv]);
    ans = dep[dv]-1;
    int now = dv;
    while(now!=du) {
        vis[now] = 1;
        now = fa[now];
    }
    Dfs2(du);
    printf("%d\n",ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}