题目大意
给定一棵$n(n \le 3 \cdot 10^5)$个点无根带边权的树
要求找出一条路径使得该路径上边权的最小值乘边权和最大
解题报告
这题啊!我们可以无脑点分对不对啊?
时间复杂度$O(n \log ^2 n)$,卡卡常数能过去
但这题更优雅的做法是维护直径
就像51nod上一个题一样,每一块内搞一个直径
合并两个块后生成的大块的直径一定在这四个点之间
于是就一路合并上去就可以辣!
时间复杂度:$O(n \log n)$
Code
点分治版本:
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300009; const int M = N << 1; const int INF = 1e9; int n,head[N],nxt[M],to[M],cost[M]; LL vout; inline void Add_Edge(int u, int v, int c) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c; } inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } class Divide_and_Conquer{ int rt,rt_sz,blk_sz,tot,sz[N],vis[N]; struct Data{ int mn,id; LL sum; inline bool operator < (const Data &B) const { return mn < B.mn; } }sta[N]; public: void solve(int w, int blk) { GetRoot(w, blk); vis[w=rt] = 1; tot = 0; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { DFS(to[i], w, to[i], cost[i], cost[i]); } } if (tot) update(); for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w]; solve(to[i], sz[to[i]]); } } } private: inline void update() { sort(sta+1, sta+1+tot); LL mx1=0,mx2=0; int sur1=0,sur2=0; for (int i=tot;i;i--) { vout = max(vout, sta[i].mn * sta[i].sum); if (sur1 && sur1 != sta[i].id) { vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn); } else if (sur2 && sur2 != sta[i].id) { vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn); } if (sta[i].sum > mx1) { if (sur1 == sta[i].id) { mx1 = sta[i].sum; } else { mx2 = mx1; sur2 = sur1; mx1 = sta[i].sum; sur1 = sta[i].id; } } else if (sta[i].sum > mx2) { if (sur1 != sta[i].id) { sur2 = sta[i].id; mx2 = sta[i].sum; } } } } inline void GetRoot(int w, int blk) { rt_sz = INF; blk_sz = blk; GetRoot1(w, w); } void GetRoot1(int w, int f) { sz[w] = 1; int mx = 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f && !vis[to[i]]) { GetRoot1(to[i], w); sz[w] += sz[to[i]]; mx = max(mx, sz[to[i]]); } } mx = max(mx, blk_sz - sz[w]); if (mx < rt_sz) rt_sz = mx, rt = w; } void DFS(int w, int f, int top, int mn, LL sum) { bool tag = 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f && !vis[to[i]]) { DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum); } } if (!tag) return; sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum; } }DAC; int main() { n = read(); for (int i=1,u,v;i<n;i++) { u = read(); v = read(); Add_Edge(u, v, read()); } DAC.solve(1, n); printf("%lld\n",vout); return 0; }
维护直径版本:
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300009; const int M = N << 1; int n,head[N],nxt[M],to[M],cost[M]; int stp[N],p[N][2],fa[N][20],anc[N]; struct Edge{int u,v,c;}e[N]; LL vout,dep[N],MX[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } void DFS(int w, int f) { fa[w][0] = f; stp[w] = stp[f] + 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { dep[to[i]] = dep[w] + cost[i]; DFS(to[i], w); } } } inline void AddEdge(int u, int v, int c, int id) { static int E = 1; cost[E+1] = cost[E+2] = c; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; e[id] = (Edge){u, v, c}; } inline LL Dis(int u, int v) { if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v; for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i]; if (u == v) return dep[p2] - dep[u]; for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2]; } int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);} inline LL Merge(int u, int v) { static LL ret, p1, p2; u = find(u); v = find(v); if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1]; else ret = MX[v], p1 = p[v][0], p2 = p[v][1]; for (int i=0;i<=1;i++) { for (int j=0;j<=1;j++) { LL cur = Dis(p[u][i], p[v][j]); if (cur > ret) { ret = cur; p1 = p[u][i]; p2 = p[v][j]; } } } anc[u] = v; MX[v] = ret; p[v][0] = p1; p[v][1] = p2; return ret; } int main() { n = read(); for (int i=1,u,v;i<n;i++) { u = read(); v = read(); AddEdge(u, v, read(), i); } DFS(1, 1); for (int j=1;j<20;j++) { for (int i=1;i<=n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; } } sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;}); for (int i=1;i<=n;i++) { anc[i] = i; p[i][0] = p[i][1] = i; } for (int i=1;i<n;i++) { LL tmp = Merge(e[i].u, e[i].v); vout = max(vout, tmp * e[i].c); } printf("%lld\n",vout); return 0; }