【BZOJ4326】运输计划

    noip考场上血崩了的一题...最后一分钟把ans赋了一个小值......

    将所有运输计划按照没有虫洞时的长度从大到小排序，虫洞一定安排在前i大的运输路径的交上。LCA乱搞维护路径即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010;
const int k2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Info {int u,v,LCA,dis;}I[maxn];

int head[maxn],next[maxn<<1],E[maxn<<1],D[maxn<<1],Ecnt;
int f[maxn][20],Dis[maxn][20],Dep[maxn];
int temp;
int n,m,ans;

inline void Add_Edge(int x,int y,int d) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=d;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;D[Ecnt]=d;}

int Q[maxn],top,tail;

void Build_Tree()
{
	Q[1]=1;top=tail=1;
	Dep[1]=1;
	while (top<=n)
	{
		int x=Q[top++];
		for (int i=head[x];i;i=next[i]) if (E[i]!=f[x][0])
		{
			Q[++tail]=E[i];
			f[E[i]][0]=x;
			Dep[E[i]]=Dep[x]+1;
			Dis[E[i]][0]=D[i];
		}
		int l=0;
		while (f[x][l]) f[x][l+1]=f[f[x][l]][l],Dis[x][l+1]=Dis[x][l]+Dis[f[x][l]][l],l++; 
	}
}

void UpOne(int &x,int t,int &dis)
{
	int l=0;
	while (k2[l+1]<=t) l++;
	while (t)
	{
		if (k2[l]<=t) dis+=Dis[x][l],x=f[x][l],t-=k2[l];
		l--;
	}
}

void Up(int &u,int &v,int &dis)
{
	int l=0;
	while (f[u][l+1]!=f[v][l+1]) l++;
	while (l>=0)
	{
		if (f[u][l]!=f[v][l]) dis+=Dis[u][l]+Dis[v][l],u=f[u][l],v=f[v][l];
		l--;
	}
	if (u!=v) dis+=Dis[u][0]+Dis[v][0],u=f[u][0],v=f[v][0];
}

void Get_Info(int u,int v,int &LCA,int &dis)
{
	int du=Dep[u],dv=Dep[v];
	dis=0;
	if (du<dv) swap(du,dv),swap(u,v);
	UpOne(u,du-dv,dis);
	Up(u,v,dis);
	LCA=u;
}

void UpOne(int &x,int t)
{
	int l=0;
	while (k2[l+1]<=t) l++;
	while (t)
	{
		if (k2[l]<=t) x=f[x][l],t-=k2[l];
		l--;
	}
}

void Up(int &u,int &v)
{
	int l=0;
	while (f[u][l+1]!=f[v][l+1]) l++;
	while (l>=0)
	{
		if (f[u][l]!=f[v][l]) u=f[u][l],v=f[v][l];
		l--;
	}
	if (u!=v) u=f[u][0],v=f[v][0];
}

int Get_Fa(int u,int v)
{
	int du=Dep[u],dv=Dep[v];
	if (du<dv) swap(du,dv),swap(u,v);
	UpOne(u,du-dv);
	Up(u,v);
	return u;
}

bool cmpi(const Info &a,const Info &b) {return a.dis>b.dis;}

struct Edge{int v,dis;};
bool cmp(const Edge &a,const Edge &b) {return a.dis<b.dis;}

Edge Q1[maxn],Q2[maxn];
int n1,n2;

void Work()
{
	ans=~0U>>1;
	sort(I+1,I+1+m,cmpi);
	I[m+1].dis=ans;
	int u=I[1].u,v=I[1].v,root=I[1].LCA;
	int tu=u,tv=v,troot;
	while (tu!=root) ++n1,Q1[n1].v=tu,Q1[n1].dis=Dis[tu][0],tu=f[tu][0];
	while (tv!=root) ++n2,Q2[n2].v=tv,Q2[n2].dis=Dis[tv][0],tv=f[tv][0];
	sort(Q1+1,Q1+1+n1,cmp);
	sort(Q2+1,Q2+1+n2,cmp);
	if (m==1) ans=I[1].dis-max(Q1[n1].dis,Q2[n2].dis);
	for (int i=1;i<=m;i++)
	{
		tu=I[i].u,tv=I[i].v,troot=I[i].LCA;
		int root_LCA=Get_Fa(troot,root);
		if (Dep[root_LCA]<Dep[root] && Dep[root_LCA]<Dep[troot]) break;
		if (troot!=root)
		{
			int utroot=Get_Fa(u,troot),vtroot=Get_Fa(v,troot),turoot=Get_Fa(tu,root),tvroot=Get_Fa(tv,root);
			if (root_LCA==root)
			{
				if (Dep[utroot]<Dep[troot] && Dep[vtroot]<Dep[troot]) break;
				if (utroot==troot)
				{
					n2=0;
					root=v=troot;
					int utu=Get_Fa(u,tu),utv=Get_Fa(u,tv);
					if (utu!=root) u=utu;
					else u=utv;
					if (u==root) break;
				}
				else
				{
					n1=0;
					root=u=troot;
					int vtu=Get_Fa(v,tu),vtv=Get_Fa(v,tv);
					if (vtu!=root) v=vtu;
					else v=vtv;
					if (v==root) break;
				}
			}
			else if (root_LCA==troot)
			{
				if (Dep[turoot]<Dep[root] && Dep[tvroot]<Dep[root]) break;
				if (turoot==root) tv=root;else tu=root;
				troot=root;
			}
		}
		if (troot==root)
		{
			int utu=Get_Fa(u,tu),utv=Get_Fa(u,tv),vtu=Get_Fa(v,tu),vtv=Get_Fa(v,tv);
			if (utu!=root) u=utu,v=vtv;
			else if (utv!=root) u=utv,v=vtu;
			else if (vtu!=root) u=utv,v=vtu;
			else u=utu,v=vtv;
			if (u==v) break;
		}
		
		
		while (n1 && (Dep[temp=Q1[n1].v]<=Dep[root] || Dep[temp]>Dep[u])) n1--;
		while (n2 && (Dep[temp=Q2[n2].v]<=Dep[root] || Dep[temp]>Dep[v])) n2--;
		ans=min(ans,max(I[i+1].dis,I[1].dis-max(Q1[n1].dis,Q2[n2].dis)));
	}
}

int main()
{
	read(n);read(m);
	for (int i=1,x,y,d;i<n;i++) read(x),read(y),read(d),Add_Edge(x,y,d);
	for (int i=1;i<=m;i++) read(I[i].u),read(I[i].v);
	Build_Tree();
	for (int i=1;i<=m;i++) Get_Info(I[i].u,I[i].v,I[i].LCA,I[i].dis);
	Work();
	printf("%d\n",ans);
	return 0;
}