C++11(clang++ 3.9) 解法, 执行用时: 1302ms, 内存消耗: 133980K, 提交时间: 2020-08-19 17:30:20

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 3e6+7;
int head[M],cnt=1;
struct EDGE{int to,nxt;ll w;}ee[M*2];
void add(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}

int sx[M][21],sy[M][21];
int n;
ll dist[M];//点i到根节点的距离
int st[M],ed[M],dep[M],lg[M*2],dp[M*2][21];
int euler[M*2],sz=0;
void dfs(int u,int fa)
{
	euler[++sz]=u;
	st[u]=sz;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=ee[i].nxt)
	{
		int v=ee[i].to;
		if(fa==v)continue;
		dist[v]=dist[u]+ee[i].w;
		dfs(v,u);
		euler[++sz]=u;
	}
	ed[u]=sz;
}
int query(int l,int r)
{
	int k=lg[r-l+1];
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
inline int lca(int u,int v)
{
	if(u==v)return u;
	int x=min(st[u],st[v]),y=max(ed[v],ed[u]);
	if(x>y)swap(x,y);
//	cout<<x<<" "<<y<<"  "<<euler[query(x,y)]<<"  "<<u<<" "<<v<<endl;
	return euler[query(x,y)];
}
inline ll dis(int x,int y)
{
	return dist[x]+dist[y]-dist[lca(x,y)]*2;
}
inline pair<int,int>cp(int a,int b,int c,int d)
{
	int x=a,y=b;
	if(dis(x,y)<=dis(a,b))x=a,y=b;
	if(dis(x,y)<=dis(a,c))x=a,y=c;
	if(dis(x,y)<=dis(a,d))x=a,y=d;
	if(dis(x,y)<=dis(b,c))x=b,y=c;
	if(dis(x,y)<=dis(b,d))x=b,y=d;
	if(dis(x,y)<=dis(c,d))x=c,y=d;
	return {x,y};
}

void gao()
{
	sz=0;
	dfs(1,0);
	for(int i=1;i<=sz;i++)
		dp[i][0]=st[euler[i]];
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j)-1<=sz;i++)
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
	
	for(int i=1;i<=n;i++)sx[i][0]=i,sy[i][0]=i;
	for(int i=1;i<=20;i++)
	for(int j=1;j + (1 << i) - 1 <= n;j++)
	{
		int a=sx[j][i-1],b=sy[j][i-1],c=sx[j+(1<<(i-1))][i-1],d=sy[j+(1<<(i-1))][i-1];
		pair<int,int> p = cp(a,b,c,d);
		sx[j][i]=p.first,sy[j][i]=p.second;
	}
}

int main()
{
	lg[0]=-1,lg[1]=0;for(int i=2;i<=6e5;i++)lg[i]=lg[i>>1]+1;
	int q,u,v,w;
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	gao();
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int k=lg[r-l+1];
		int a,b,c,d;
		a=sx[l][k],b=sy[l][k];
		c=sx[r-(1<<k)+1][k],d=sy[r-(1<<k)+1][k];
		pair<int,int> p = cp(a,b,c,d);
		printf("%lld\n",dis(p.first,p.second));
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 2801ms, 内存消耗: 86028K, 提交时间: 2022-11-07 14:07:10

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=300007;
int dis[N],sz[N],d[N],son[N],fa[N],top[N];
vector<pair<int,int> >G[N];
void dfs1(int x,int father){
	d[x]=d[father]+1;
	sz[x]=1;
	son[x]=0;
	fa[x]=father;
	for(auto [i,w]:G[x]){
		if(i==father)continue;
		dis[i]=dis[x]+w;
		dfs1(i,x);
		sz[x]+=sz[i];
		if(!son[x]||sz[son[x]]<sz[i])
			son[x]=i;
	}
}
void dfs2(int x,int topx){
	top[x]=topx;
	if(son[x])
		dfs2(son[x],topx);
	for(auto [i,w]:G[x]){
		if(i==fa[x]||i==son[x])continue;
		dfs2(i,i);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]){
			swap(x,y);
		}
		x=fa[top[x]];
	}
	if(d[x]>d[y])
		swap(x,y);
	return x;
}
int dis1(pair<int,int>a){
	int x=a.first,y=a.second;
	return dis[x]+dis[y]-2*dis[lca(x,y)];
}
pair<int,int> Max(pair<int,int> a,pair<int,int> b){
	if(dis1(a)>dis1(b))
		return a;
	else 
		return b;
}
struct node{
	int l,r;
	pair<int,int>ans;
	node friend operator +(node a,node b){
		node c;
		c.l=a.l;
		c.r=b.r;
		auto [x1,y1]=a.ans;
		auto [x2,y2]=b.ans;
		pair<int,int>tmp;
		tmp=Max({x1,y1},Max({x1,x2},{x1,y2}));
		tmp=Max(Max({y1,x2},{y1,y2}),tmp);
		tmp=Max(tmp,{x2,y2});
		c.ans=tmp;
		return c;
	}
}t[N<<2];
void pushup(int k){
	t[k]=t[k<<1]+t[k<<1|1];
};
void build(int k,int l,int r){
	if(l==r){
		t[k].l=l;
		t[k].r=r;
		t[k].ans={l,l};
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
node query(int k,int l,int r){
	if(l<=t[k].l&&t[k].r<=r){
		return t[k];
	}
	int mid=(t[k].l+t[k].r)>>1;
	if(r<=mid)
		return query(k<<1,l,r);
	else if(l>mid)
		return query(k<<1|1,l,r);
	else 
		return query(k<<1,l,r)+query(k<<1|1,l,r);
}
int32_t main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dfs1(1,1);
	dfs2(1,1);
	build(1,1,n);
	while(q--){
		int l,r;
		cin>>l>>r;
        //cout<<l<<" "<<r<<endl;
		node ans=query(1,l,r);
        //cout<<ans.l<<" "<<ans.r<<" "<<ans.ans.first<<" "<<ans.ans.second<<'\n';
		cout<<dis1(ans.ans)<<'\n';
	}
}

C++14(g++5.4) 解法, 执行用时: 2526ms, 内存消耗: 107528K, 提交时间: 2020-08-14 22:38:05

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,M=N<<1;
int n,m,pos[N],bl[N],dep[N],f[N],son[N],sz[N],cnt,d[N];
int head[N],nex[M],to[M],w[M],tot;
struct node{int x,y,w;}t[N<<2],c;
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]) if(to[i]!=f[x]){
		dep[to[i]]=dep[x]+1,d[to[i]]=d[x]+w[i],f[to[i]]=x;
		dfs1(to[i]); sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]]) son[x]=to[i];
	}
}
void dfs2(int x,int belong){
	pos[x]=++cnt; bl[x]=belong;
	if(son[x])	dfs2(son[x],belong);
	for(int i=head[x];i;i=nex[i]) if(to[i]!=son[x]&&to[i]!=f[x]) dfs2(to[i],to[i]);
}
inline int lca(int x,int y){
	while(bl[x]!=bl[y]){
		if(dep[bl[x]]<dep[bl[y]])	swap(x,y);	x=f[bl[x]];
	}
	return dep[x]>dep[y]?y:x;
}
inline int dis(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
#define mid (l+r>>1)
inline node merge(node a,node b){
	c=(a.w>b.w?a:b); int tmp;
	if((tmp=dis(a.x,b.x))>c.w) c={a.x,b.x,tmp};
	if((tmp=dis(a.x,b.y))>c.w) c={a.x,b.y,tmp};
	if((tmp=dis(a.y,b.x))>c.w) c={a.y,b.x,tmp};
	if((tmp=dis(a.y,b.y))>c.w) c={a.y,b.y,tmp};
	return c;
}
void build(int p,int l,int r){
	if(l==r){t[p].x=l,t[p].y=l,t[p].w=0; return ;}
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	t[p]=merge(t[p<<1],t[p<<1|1]);
}
node ask(int p,int l,int r,int ql,int qr){
	if(l==ql&&r==qr)	return t[p];
	if(qr<=mid) return ask(p<<1,l,mid,ql,qr);
	else if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);
	else return merge(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));
}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b,c;i<n;i++) scanf("%lld %lld %lld",&a,&b,&c),add(a,b,c),add(b,a,c);
	dfs1(1),dfs2(1,1),build(1,1,n);
	for(int i=1,l,r;i<=m;i++) 
		scanf("%lld %lld",&l,&r),printf("%lld\n",ask(1,1,n,l,r).w);
	return 0;
}