题解 P3304 【[SDOI2013]直径】

lx_zjk

2019-10-28 18:41:04

Solution

来写一份题解吧 这好像是近期我的第一篇题解 首先这道题目需要了解树的直径的一个性质 数的直径必须经过一个点 且这个点为这个直径的中点 反证法: 假设有两条不相交的直径 因为树上任意两点都有一条唯一的路径 那么假设连接两个中点的长度为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; } ```