sxczf's Blog

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=4326

好像少了数据范围n,m<=300000

一开始的思路是二分然后树链剖分之类的。。然后想了半天不会做。

于是先考虑只有一条链的情况也就是区间询问

首先最后删的边一定在删边前答案最大的询问上

把询问按答案从大到小排序

假设我们删一条边i，设不包含它的最大的询问是k

那么答案就是max(询问max-cost[i],询问[k])

解释一下：包含它的询问答案都要减去cost[i],其中最大的就是答案最大的那个询问

不包含它的询问中答案最大的就是 k这个询问的答案

这个怎么计算呢

把询问区间从大到小一个个交起来

新加入一个询问K后，交就(可能)会变小

减小的这段区间的"k"就是当前的询问K

可以用奇怪的姿势在nlogn及以下的时间内进行计算

好了我们会写一条链上的询问了

然后想想树上的怎么做

只要把最大的询问那条链拎出来然后就转化为链上的询问了

其他的询问可以转化为2条树链的交

比如最大的询问是1-2-3-4-5

比如一个询问是6-7-3-4-8-9-10

其实只要3-4这段就够了

然后就解决了

效率O(nlog(n))

#include <cstdio>
#include <algorithm>
#define N 300005
using namespace std;
int a,b,c,d[N],e[N],f,g,h,i,j,k,l,m,n,r,tot,Tot;
int way[N*2],next[N*2],last[N],cost[N*2];
int Way[N*2],Next[N*2],Last[N],From[N*2];
int Fa[N],fa[N],dis[N],Dis[N],cfa[N],sd[N],se[N],from[N],vis[N];
struct node{int u,v,ans,lca;}work[N];
inline bool cmp(const node &a,const node &b){return a.ans>b.ans;}
void make(int a,int b,int c){
	way[++tot]=b;next[tot]=last[a];last[a]=tot;cost[tot]=c;
	way[++tot]=a;next[tot]=last[b];last[b]=tot;cost[tot]=c;
}
void Make(int a,int b,int c){
	Way[++Tot]=b;Next[Tot]=Last[a];Last[a]=Tot;From[Tot]=c;
	Way[++Tot]=a;Next[Tot]=Last[b];Last[b]=Tot;From[Tot]=c;
}
int get(int x){if(Fa[x]==x)return x;return Fa[x]=get(Fa[x]);}
void Dfs(int x,int a,int b,int s){
	from[x]=s;
	for(int i=last[x];i;i=next[i])
	if(way[i]!=a&&way[i]!=b)Dfs(way[i],x,0,s);
}
void dfs(int x){
	Fa[x]=x;vis[x]=1;
	for(int i=last[x];i;i=next[i])
	if(way[i]!=fa[x]){
		fa[way[i]]=x;cfa[way[i]]=cost[i];
		dis[way[i]]=dis[x]+cost[i];
		Dis[way[i]]=Dis[x]+1;
		dfs(way[i]);
	}
	for(int i=Last[x];i;i=Next[i])
	if(vis[Way[i]])work[From[i]].lca=get(Way[i]);
	Fa[x]=fa[x];
}
inline int in(){
	int x=0;char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	if(m==0){printf("0");return 0;}
	for(i=1;i<n;i++){
		a=in();b=in();c=in();
		make(a,b,c);
	}
	for(i=1;i<=m;i++){
		a=in();b=in();
		Make(a,b,i);
		work[i].u=a;work[i].v=b;
	}
	for(i=1;i<=n+1;i++)Fa[i]=i;
	Dis[1]=1;dfs(1);
	for(i=1;i<=m;i++)work[i].ans=dis[work[i].u]+dis[work[i].v]-dis[work[i].lca]*2;
	sort(work+1,work+1+m,cmp);
	if(work[1].ans==0){printf("0");return 0;}
	h=work[1].ans;
	for(i=1;i<=n+1;i++)Fa[i]=i;
	for(i=work[1].u;i!=work[1].lca;i=fa[i]){
		d[++d[0]]=i;sd[d[0]]=cfa[i];
	}
	for(i=work[1].v;i!=work[1].lca;i=fa[i]){
		e[++e[0]]=fa[i];se[e[0]]=cfa[i];
	}
	for(i=d[0]+1;i<=d[0]+e[0];i++)d[i]=e[e[0]-i+d[0]+1],sd[i]=se[e[0]-i+d[0]+1];d[0]+=e[0];
	d[++d[0]]=work[1].v;
	Dfs(d[1],d[2],0,1);
	Dfs(d[d[0]],d[d[0]-1],0,d[0]);
	for(i=2;i<d[0];i++)Dfs(d[i],d[i-1],d[i+1],i);
	for(i=2;i<=m;i++){
		int U=from[work[i].u],V=from[work[i].v];
		if(U>V)swap(U,V);
		for(j=1;j<U;){
			j=get(j);
			if(j>=U)break;
				Fa[j]=j+1;h=min(h,max(work[1].ans-sd[j],work[i].ans));
		}
		for(j=V;j<d[0];){
			j=get(j);
			if(j>=d[0])break;
			Fa[j]=j+1;h=min(h,max(work[1].ans-sd[j],work[i].ans));
		}
	}
	for(i=1;i<=d[0];i++)if(Fa[i]==i)h=min(h,work[1].ans-sd[i]);
	printf("%d\n",h);
	return 0;
}