orz n+e的題解

顯然，將兩棵樹合并以后，新直徑的兩個端點一定在原來的兩條直徑的四個端點中。

畫個圖就知道了（我竟然沒看出來QAQ

于是就可以從大到小枚舉最小權，并查集合并了

時間復雜度\(O(nlogn)\)

?

#include <bits/stdc++.h> #define N 60000 using namespace std; int n; int vi[N]; vector <int> bi[N]; int shed[N], fa[N], fp[N], dep[N], fb[N]; int lowbit(int t) {return t & (-t);} void dfs(int t, int d) {shed[d] = t; dep[t] = d; fa[t] = shed[d - 1]; fp[t] = shed[d - lowbit(d)];for (int i = 0; i < bi[t].size(); ++ i)if (bi[t][i] != fa[t])dfs(bi[t][i], d + 1); } int lca(int a, int b) {while (a != b){if (dep[a] < dep[b]) swap(a, b);if (dep[a] > dep[b]){if (dep[fp[a]] < dep[b]) a = fa[a];else a = fp[a];}else {if (fp[a] == fp[b]) a = fa[a], b = fa[b];else a = fp[a], b = fp[b];}}return a; } int get_fb(int t) {return fb[t] = fb[t] == t? t: get_fb(fb[t]); } int ai[N][2]; int ls[N], vis[N]; int comp(int a, int b) {return vi[a] > vi[b];} #define LL long long LL ans; int main() {scanf("%d", &n);for (int i = 1; i <= n; ++ i)scanf("%d", &vi[i]);for (int i = 1; i <= n; ++ i) ls[i] = ai[i][0] = ai[i][1] = fb[i] = i;sort(ls + 1, ls + n + 1, comp);for (int i = 1; i < n; ++ i){int a, b;scanf("%d%d", &a, &b);bi[a].push_back(b);bi[b].push_back(a);}dfs(1, 1);for (int q = 1; q <= n; ++ q){int i = ls[q], mx = 0;vis[i] = 1;for (int j = 0; j < bi[i].size(); ++ j)if (vis[bi[i][j]]){int x = get_fb(bi[i][j]);int ll[4] = {ai[x][0], ai[x][1], ai[i][0], ai[i][1]};for (int p0 = 0; p0 < 4; ++ p0)for (int p1 = p0 + 1; p1 < 4; ++ p1){int nw = dep[ll[p0]] + dep[ll[p1]] - dep[lca(ll[p0], ll[p1])] * 2;if (nw > mx){mx = nw;ai[i][0] = ll[p0];ai[i][1] = ll[p1];}}fb[x] = i;}ans = max(ans, 1ll * (mx + 1) * vi[i]);}cout << ans; }

?

轉載于:https://www.cnblogs.com/AwD-/p/6329538.html

總結

以上是生活随笔為你收集整理的bzoj 2870: 最长道路tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。