题解 P3304 【[SDOI2013]直径】

这是由一次题解都没有过审核的菜鸡为您带来的题解qwq 这个题我做的时候没有看题解，也没有想到所有直径交于一些连续的边这种事情，其实也很好想，但我的思路并不在这上面。 首先第一问可以dfs/bfs/dp，这个无所谓，但是要注意记得求出一种直径方案，便于我们处理第二问 我们首先分析，如果一个边一定在直径上的话，那么很显然，我去掉这个边之后，所分成的两棵子树，它们的直径一定小于原树的直径，不然这个边就不一定在直径上了，有可能会存在别的直径方案不覆盖这条边。 那么问题可以转化成求去掉某种直径的某一条边后，新形成的两棵子树的直径，这个东西如果暴力枚举去掉哪条边的话，很显然坠坏的时间复杂度是n^2的。然后我们想这个地方有没有重复的，可以优化的部分。回想一下树形dp求树的直径的过程，我们求一棵树的直径的时候，它的所有子树一定都是处理好的。那么很显然我们如果断开一条边的时候，有直径起点的那一部分子树，很显然可以通过以直径终点为根跑树形dp来处理看，反之亦然。 这样我们就轻松去掉了一个n，总的时间复杂度变为了O(n)。当然两边bfs+两边dfs会使得常数比较大，但是总的来说还是很轻松的就能过的。 如果有写的不好的地方请多指教qwq。 ```cpp #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define ri register int using namespace std; inline char gch() { static char buf[100010], *h = buf, *t = buf; return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++; } typedef long long lo; inline void re(int &x) { x = 0; char a; bool b = 0; while(!isdigit(a = gch())) b = a == '-'; while(isdigit(a)) x = (x << 1) + (x << 3) + a - '0', a = gch(); if(b == 1) x *= -1; } int n, s, t, he, ta, tot = -1, pos, q[200020], head[200020], pre[200020], lx, ly, lz; struct in { int to, ne; lo co; }ter[400040]; inline void build(int f, int l, lo c) { ter[++ tot] = (in){l, head[f], c}, head[f] = tot; ter[++ tot] = (in){f, head[l], c}, head[l] = tot; } lo ans, sx[200020], tx[200020], sy[200020], ty[200020], de[200020];//x 联通块直径 y最深深度 inline void bfs(int x) { memset(de, 0, sizeof(de)), memset(pre, 0, sizeof(pre)); de[q[he = ta = 0] = x] = 1, pos = 0; while(he <= ta) { int qaq = q[he ++]; pos = (de[pos] < de[qaq]) ? qaq : pos;//更新最深的点 for(ri i = head[qaq]; i >= 0; i = ter[i].ne) { int to = ter[i].to; if(de[to] == 0) pre[to] = qaq, de[q[++ ta] = to] = de[qaq] + ter[i].co; } } } void dfs(lo *a, lo *b, int no, int fa) { lo lx = 0, ly = 0; for(ri i = head[no]; i >= 0; i = ter[i].ne) { int to = ter[i].to; if(to == fa) continue; dfs(a, b, to, no); b[no] = (b[no] < b[to] + ter[i].co) ? b[to] + ter[i].co : b[no]; if(lx < b[to] + ter[i].co) ly = lx, lx = b[to] + ter[i].co; else if(ly < b[to] + ter[i].co) ly = b[to] + ter[i].co; a[no] = (a[no] < a[to]) ? a[to] : a[no];//维护子树内部的直径 } a[no] = (lx + ly < a[no]) ? a[no] : lx + ly; } int main() { re(n); memset(head, -1, sizeof(head)); s = t = 0; memset(sx, 0, sizeof(sx)), memset(sy, 0, sizeof(sy)); memset(tx, 0, sizeof(tx)), memset(ty, 0, sizeof(ty)); for(ri i = 1; i < n; i ++) re(lx), re(ly), re(lz), build(lx, ly, lz); bfs(1), s = pos, bfs(s), t = pos;//两边bfs确定任意一条直径 dfs(sx, sy, s, 0), dfs(tx, ty, t, 0);//分别以起点和终点为根再去处理子树的信息 for(ri i = t; i != s; i = pre[i]) if(tx[pre[i]] < sx[s] && sx[i] < sx[s])//如果删除这条边之后，两个子树内的直径都小于原树直径 ans ++;//说明这个边一定被所有直径经过 printf("%lld\n%lld", sx[s], ans); } ```