NOIP2015运输计划
唉
真是
这题
卡死我了
tarjan离线lca复杂度O（n）
最后各种卡常，多交几遍才A（洛谷104ms）
%%%zk学长609ms
注意二分的时候左边界要定成0
根据题意，显然先想到二分，然后求交集，在集合里找有没有边删掉之后使得所有路长度<mid
#include<bits/stdc++.h>
using namespace std;
char *TT,*mo,but[(<<)+];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin)),TT==mo)?0:*TT++)
inline int read(){
int x=,c=,f=;
for(;c<''||c>'';c=getchar())f=c!='-';
for(;c>=''&&c<='';c=getchar())x=x*+c-'';
return f?x:-x;
}
int root;
struct Q{
int a,b,lca,len;
}q[];
int head1[];
bool comp(Q A,Q B){
return A.len>B.len;
}
struct T1{
int next,to,num;
}e1[];
int cnt1;
void add1(int u,int v,int c){
e1[++cnt1].to=v;e1[cnt1].next=head1[u];e1[cnt1].num=c;head1[u]=cnt1;
}
struct T{
int next,to,cal;
}e[];
int cnt;
int head[];
int deep[];
int p[];
void add(int u,int v,int c){
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].cal=c;head[u]=cnt;
}
int sum[];
int n,m;
int fa[];
int find(int x){
return !(fa[x]^x)?x:fa[x]=find(fa[x]);
}
void un(int x,int y){
x=find(x),y=find(y);
if(x^y)fa[x]=y;
}
bitset<>vis;
void init(int u){
vis[u]=;
for(int i=head[u];i;i=e[i].next){
if(vis[e[i].to])continue;
deep[e[i].to]=deep[u]+e[i].cal;
p[e[i].to]=e[i].cal;
init(e[i].to);
un(e[i].to,u);
}
for(int i=head1[u];i;i=e1[i].next){
int v=e1[i].to;
int ms=e1[i].num;
if(vis[v]!=){
q[ms].lca=find(v);
}
}
}
void dfs(int faf,int u){
for(int i=head[u];i;i=e[i].next){
if(!(e[i].to^faf))continue;
dfs(u,e[i].to);
sum[u]+=sum[e[i].to];
}
}
bool check(int mid){
memset(sum,,sizeof(sum));
int ret=;
register int i,j;
for(i=;i<=m;i++){
if(q[i].len<=mid)break;
sum[q[i].a]++;
sum[q[i].b]++;
sum[q[i].lca]-=;
ret=max(ret,q[i].len-mid);
}
i--;
dfs(,root);
for(j=;j<=n;j++){
if(p[j]>=ret&&sum[j]==i)return ;
}
return ;
}
int main(){
srand(time(NULL));
n=read(),m=read();
for(int i=;i<=n;i++)fa[i]=i;
int x,y,z;
for(int i=;i<n;i++){
x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,z);
}
root=rand()%n+;
deep[root]=;
for(int i=;i<=m;i++){
q[i].a=read(),q[i].b=read();
add1(q[i].a,q[i].b,i);
add1(q[i].b,q[i].a,i);
}
init(root);
for(int i=;i<=m;i++){
q[i].len=deep[q[i].a]+deep[q[i].b]-*deep[q[i].lca];
}
sort(q+,q+m+,comp);
int l=,r=;
while(r>l){
int mid=l+r>>;
//cout<<mid<<endl;
if(check(mid))r=mid;
else l=mid+;
}
cout<<l;
return ;
}