【日常小测】路径规划

题目大意

给定一棵$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;
}