题意:给一棵树 选三个点A,B,C 求A到B的再从B到C的距离最大值 需要满足AB的距离小于AC的距离
题解:首先树上的最大距离就想到了直径 但是被样例误导了TAT
BC两点构成了直径 我一开始以为A在直径上答案最大 然后再加上最接近路径长度一半的路径
其实 A不在直径上的话显然更优啊...
那么做法就是先求出直径 然后记录路径 枚举路上的每一个点能到达的最远的路径
当然这个最远路径不能和直径有公共边
复杂度的话想想还挺有意思的 从直径上走刚好遍历整棵树
总结:突然发现这个题数据水了..
我这个写法 在枚举直径路上的点的时候每一次都暴力memset
假设这棵树是一条链肯定会超时的...
如果这样的话写法就应该枚举每个点的时候把dfs到的点放进数组里
然后再把这些点手动清空 反正过了 懒得改了..
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; typedef long long ll; int n, m, l, r, cnt, num, rt; ll ans1, ans2, zd; struct node { int to, nex, val; }E[400005]; int head[200005]; int pre[200005]; int vis[200005]; int lian[200005]; ll dis[200005]; ll diss[200005]; void dfs(int x, int fa) { pre[x] = fa; int c = head[x]; for(int i = c; i; i = E[i].nex) { int v = E[i].to; if(v == fa) continue; dis[v] = dis[x] + E[i].val; dfs(v, x); } if(dis[x] > dis[rt]) rt = x; } void dfs1() { int x = r; while(x != pre[l]) { num++; lian[num] = x; vis[x] = 1; x = pre[x]; } } void dfs2(int x, int fa) { int c = head[x]; for(int i = c; i; i = E[i].nex) { int v = E[i].to; if(v == fa) continue; if(vis[v]) continue; diss[v] = diss[x] + E[i].val; dfs2(v, x); } zd = max(zd, diss[x]); } int main() { ans1 = 0; ans2 = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v, o; scanf("%d%d%d", &u, &v, &o); E[++cnt].to = v; E[cnt].nex = head[u]; head[u] = cnt; E[cnt].val = o; E[++cnt].to = u; E[cnt].nex = head[v]; head[v] = cnt; E[cnt].val = o; } dfs(1, -1); l = rt; memset(dis, 0, sizeof(dis)); dfs(rt, -1); r = rt; ans1 = dis[r]; dfs1(); for(int i = 1; i <= num; i++) { memset(diss, 0, sizeof(diss)); zd = 0; dfs2(lian[i], -1); ll tmp = zd + min(dis[lian[i]], ans1 - dis[lian[i]]); ans2 = max(ans2, tmp); } printf("%lld ", ans1 + ans2); return 0; }