题解 P3304 【[SDOI2013]直径】
lx_zjk
2019-10-28 18:41:04
来写一份题解吧 这好像是近期我的第一篇题解
首先这道题目需要了解树的直径的一个性质
数的直径必须经过一个点 且这个点为这个直径的中点
反证法:
假设有两条不相交的直径
因为树上任意两点都有一条唯一的路径
那么假设连接两个中点的长度为len, 直径长度为max_d
那么两条直径的两端距离为max_d + len > max_d
那么直径长度不是len
矛盾
所以两条直径必须经过一个点
同理证明这个点是中点 也可以用相同方法 ~~易证~~
那么有了这个的话 做这道题应该好做多了 先两遍$dfs$跑出$l$$和r$
然后对于两个端点所经过的路径上 跑一遍$dfs$ 如果$maxd == dis$那么就说明那个点不是必须点 可以$pass$ 然后就可以了
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2139062143;
#define DEBUG(x) std::cerr << #x << " = " << x << std::endl
inline ll read() {
ll f = 1, x = 0;char ch;
do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');
do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
return f * x;
}
const int MAX_N = 2e5 + 7;
struct EDGE {
int to, next, w;
} edge[MAX_N << 1];
int head[MAX_N], E;
void addedge (int u, int v, int w) {
edge[++E].to = v;
edge[E].next = head[u];
edge[E].w = w;
head[u] = E;
}
int n, ans, f[MAX_N], vis[MAX_N], p, l, r;
ll dep[MAX_N], max_d;
inline void dfs (int u, int fa) {
f[u] = fa;
for (int i = head[u]; i; i = edge[i].next ) {
int v = edge[i].to, w = edge[i].w;
if (v == fa) continue;
dep[v] = dep[u] + w;
if (dep[v] > max_d) {
max_d = dep[v];
p = v;
}
dfs (v, u);
}
}
inline void dfs2 (int u, int fa) {
for (int i = head[u]; i; i = edge[i].next ) {
int v = edge[i].to, w = edge[i].w;
if (vis[v] || fa == v) continue;
dep[v] = dep[u] + w;
if (dep[v] > max_d) max_d = dep[v];
dfs2 (v, u);
}
}
int main() {
n = read ();
for (int i = 1; i < n; i ++ ) {
int u = read (), v = read (), w = read ();
addedge (u, v, w);
addedge (v, u, w);
}
dfs (1, 0);
l = p;
max_d = 0;
dep[p] = 0;
dfs (l, 0);
r = p;
printf ("%lld\n", max_d);//开longlong
bool flag = 0;
for (int i = r; i; i = f[i]) vis[i] = 1;
int ll = l, rr = r;
for (int i = f[rr]; i != ll; i = f[i]) {
int l_dis = dep[i], r_dis = dep[rr] - dep[i];
dep[i] = max_d = 0;
dfs2 (i, 0);
//l找最右 r找最左 所以l只需要找一次就行了
if (max_d == r_dis)
r = i;
if (max_d == l_dis && !flag) {
flag = 1;
l = i;
}
}
int ans = 1;//为什么初始化ans = 1 因为后面 (i != l) 没有把l算进去
for (int i = f[r]; i != l; i = f[i]) ans ++ ;
cout << ans << endl;
return 0;
}
```