路径规划
题目背景：
thoj27
分析：这道题我打了一个暴力，用树链剖分实现不知道为什么前两个点都没有过，但是别人完全不优化的暴力竟然都过了，这样我很不服啊，不开心qnq，本来呢，这道题敲一个无脑的点分是可以卡卡常数过的，复杂度O(nlog2n)，但是正如某学长所说，这样非常的不优雅，那我们考虑一些优雅些的做法，首先我们这里给出一个结论。对于树上的两个不相交的点集S，T，若集合S中的最长链（即直径）是Sx à Sy，集合T内的最长链（直径）是Tx à Ty 那么如果我们合并这两个点集，那么现在的合并的点集的最长链（直径）一定是，Sx à Sy, Sx à Tx, Sx à Ty, Sy à Tx, Sy à Ty, Tx à Ty这6条中的一个，那现在问题就简单了，我们将树边按照边权由大到小直接排序，对于然后维护连通块直径，每一次将边两端的连通块合并，然后更新新的直径就可以了，这样的复杂度为O(nlogn)
Source：
#include #include #include #include #include #include #include #include using namespace std; inline char read() { static const int IN_LEN = 1024 * 1024; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; } template inline bool R(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return false; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x << 3) + (x << 1) + (c ^ '0'); if (iosig) x = -x; return true; } const int OUT_LEN = 1024 * 1024; char obuf[OUT_LEN], *oh = obuf; inline void writechar(char c) { if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf; *oh++ = c; } template inline void W(T x) { static int buf[30], cnt; if (!x) writechar(48); else { if (x < 0) writechar('-'), x = -x; for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48; while (cnt) writechar(buf[cnt--]); } } inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); } const int MAXN = 300000 + 10; struct data { int u, v, w; data(int u, int v, int w) : u(u), v(v), w(w) {} data() {} bool operator < (const data &a) const { return w > a.w; } } side[MAXN]; struct node { int to, w; node(int to, int w) : to(to), w(w) {} node() {} }; vector edge[MAXN]; struct Tree { int top; int size; int son; int father; int dis; int dep; int num; } tree[MAXN]; struct comp { int x, y; comp(int x, int y) : x(x), y(y) {} comp() {} } dis[MAXN]; int ind, n, x, y, z; int father[MAXN], pos[MAXN]; inline void addEdge(int u, int v, int w) { edge[u].push_back(node(v, w)); edge[v].push_back(node(u, w)); } inline void dfs1(int cur, int fa, int w) { tree[cur].size = 1; tree[cur].father = fa; tree[cur].dis = tree[fa].dis + w;; tree[cur].dep = tree[fa].dep + 1; for (int p = 0; p < edge[cur].size(); ++p) if (edge[cur][p].to != fa) { dfs1(edge[cur][p].to, cur, edge[cur][p].w); tree[cur].size += tree[edge[cur][p].to].size; if (!tree[cur].son || tree[tree[cur].son].size < tree[edge[cur][p].to].size) tree[cur].son = edge[cur][p].to; } } inline void dfs2(int cur, int top) { tree[cur].top = top; tree[cur].num = ++ind; pos[ind] = cur; if (tree[cur].son) dfs2(tree[cur].son, top); for (int p = 0; p < edge[cur].size(); ++p) if (!tree[edge[cur][p].to].num) dfs2(edge[cur][p].to, edge[cur][p].to); } /*这里的树链剖分只是用来求lca*/ inline int query_length(int u, int v) { int p = u, q = v; while (tree[u].top != tree[v].top) { int x = tree[u].top, y = tree[v].top; if (tree[x].dep > tree[y].dep) u = tree[x].father; else v = tree[y].father; } if (tree[u].dep > tree[v].dep) return tree[p].dis + tree[q].dis - 2 * tree[v].dis; else return tree[p].dis + tree[q].dis - 2 * tree[u].dis; } inline void readin() { R(n); for (int i = 1; i < n; ++i) { R(x), R(y), R(z); addEdge(x, y, z); side[i] = data(x, y, z); } } inline int getfather(int x) { return (father[x] == x) ? x : (father[x] = getfather(father[x]), father[x]); } inline bool update(long long &x, int y) { return (x < y) ? (x = y, true) : false; } inline void work() { long long ans = 0; sort(side + 1, side + n); for (int i = 1; i <= n; ++i) father[i] = i, dis[i] = comp(i, i); for (int i = 1; i < n; ++i) { int fa1 = getfather(side[i].u), fa2 = getfather(side[i].v); long long cur = 0; int x1 = dis[fa1].x, y1 = dis[fa1].y; int x2 = dis[fa2].x, y2 = dis[fa2].y; int a, b; if (update(cur, query_length(x1, y1))) a = x1, b = y1; if (update(cur, query_length(x1, x2))) a = x1, b = x2; if (update(cur, query_length(x1, y2))) a = x1, b = y2; if (update(cur, query_length(y1, x2))) a = y1, b = x2; if (update(cur, query_length(y1, y2))) a = y1, b = y2; if (update(cur, query_length(x2, y2))) a = x2, b = y2; father[fa1] = fa2, dis[fa2] = comp(a, b); ans = max(ans, 1LL * side[i].w * query_length(a, b)); } W(ans); } int main() { // freopen("in.in", "r", stdin); readin(); dfs1(1, 1, 0); dfs2(1, 1); work(); flush(); return 0; }