挺进

挺进

题意：给你一颗树，要求断掉一条边，使得剩下两个联通快的直径之和最大

假设我们枚举断哪一条边，在logn时间内求出两个联通快的直径（树剖lca) 不就行了嘛

怎么做呢，我们发现，可以用树的dfs序来维护，我们用一个线段树维护一个区间内的直径的端点和长度

如何合并呢？

我们假设两块的直径端点分别为x1,y1,x2,y2，那么结果就是在这四个点中取2个的所有方案的最大值

具体细节见代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
// typedef long long int;
const int N=200010;
inline int read() {
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return x;
}

int n;
int hd[N],tot,to[N],nxt[N],w[N];
inline void add(int x,int y,int z) {
	to[++tot]=y;w[tot]=z;nxt[tot]=hd[x];hd[x]=tot;
}

int dis[N];
int fa[N],dep[N],siz[N],son[N];
void dfs_son(int x,int f) {
	fa[x]=f;siz[x]=1;dep[x]=dep[f]+1;
	for(int i=hd[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==f) continue;
		dis[y]=dis[x]+w[i];
		dfs_son(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}

int dfnin[N],dfnout[N],rev[N],top[N],dfn_cnt;
void dfs_chain(int x,int tp) {
	top[x]=tp;
	dfnin[x]=++dfn_cnt;rev[dfn_cnt]=x;
	if(son[x]) dfs_chain(son[x],tp);
	for(int i=hd[x];i;i=nxt[i]) {
		int y=to[i];
		if(dfnin[y]) continue;
		dfs_chain(y,y);
	}	
	dfnout[x]=dfn_cnt;
}

inline int get_dia(int x,int y) {
	if(!x||!y) return 0;
	int sum=dis[x]+dis[y];
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return sum-(dep[x]<dep[y]?dis[x]:dis[y])*2;
}

struct TREE{
	int x,y;
	int v;
	TREE() {}
	TREE(int x_,int y_,int v_) {x=x_;y=y_;v=v_;}
}t[N<<1];
TREE Max(TREE a,TREE b) {return a.v<b.v?b:a;}
TREE get(int a,int b) {return TREE(a,b,get_dia(a,b));}
TREE merge(TREE a,TREE b) {
	return Max(Max(a,b),Max(Max(get(a.x,b.x),get(a.y,b.y)),Max(get(a.x,b.y),get(a.y,b.x))));
}
void build(int l,int r,int p) {
	if(l==r) {
		t[p]=TREE(rev[l],rev[l],0);
		return;
	}
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[p]=merge(t[ls],t[rs]);
}
TREE query(int l,int r,int L,int R,int p) {
	if(L>R) return TREE(0,0,0);
	if(L<=l&&r<=R) return t[p];
	TREE res=TREE(0,0,-1);
	if(L<=mid) res=query(l,mid,L,R,ls);
	if(R>mid) res=merge(res,query(mid+1,r,L,R,rs));
	return res;
}
signed main() {
	n=read();
	for(int i=1,x,y,z;i<n;i++) {
		x=read();y=read();z=read();
		add(x,y,z);
		add(y,x,z);
	}
	dfs_son(1,0);
	dfs_chain(1,1);
	build(1,n,1);
	int ans=0;
	for(int i=1;i<n;i++) {
		TREE a=query(1,n,dfnin[i],dfnout[i],1);
		TREE b=query(1,n,1,dfnin[i]-1,1);
		TREE c=query(1,n,dfnout[i]+1,n,1);
		ans=max(ans,a.v+merge(b,c).v);
	}
	printf("%lld
",ans);
	return 0;
}