cogs2109 [NOIP2015] 運輸計劃
二分答案+樹上差分。
STO鏈剖巨佬們我不會（太虛偽了吧
首先二分一個答案，下界為0,上界為max{路徑長度}。
然后判斷一個答案是否可行，這里用到樹上差分。
（闊以理解為前綴和？？？）
隨便搞出所有路徑的LCA。
倍增可能會MLE，Trajan（沒拼錯）不會，只會鏈剖求LCA。
對于一個mid，所有路徑>mid的路徑都需要減一個值。設有k條。這個排序后二分求（mdzz二分寫跪N多次）
由于只能
把一條路權值置0，這條路肯定要在k條路的交上，而且一定是權值最大的那個
如何搞出k條路的交？樹剖+樹狀數組，每次把路上所有邊權++，然后檢查那些邊權是k的邊，選一個最大怎么可能= =（雖然可做OTZ）
然后搞一個差分數組h，h[i]表示i到1所有點的共同增量（相當于樹狀數組維護的值得共同增量）
每次一條路徑x<->y
h[x]++,h[y]++,h[lca(x,y)]-=2
然后x-y路徑上的點都加上了1
最后只需要從下往上一路加即可
OTZ。。。
然后，就沒有然后了。
如果沒有這樣的路，check返回0，
如果有，check返回（最長路徑的長度-找出的最長路的長度>=mid）。
不解釋。
PS.有氧氣比沒氧氣慢？！
Code
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){rg int x=0;rg bool flg=0;rg char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return flg?-x:x;
}
int n,m;
const int maxn=300010,maxm=300010<<1;
int fir[maxn],dis[maxm],nxt[maxm],w[maxm],d[maxm],id;
il vd add(const int&a,const int&b,const int&c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
struct plan{int x,y,lca,len;}s[maxn];
il bool cmp(const plan&a,const plan&b){return a.len>b.len;}
int fa[maxn],top[maxn],siz[maxn],dep[maxn],tot[maxn],son[maxn],r[maxn];
il vd dfs_(const int&x){siz[x]=1;erep(i,x)if(dis[i]^fa[x]){fa[dis[i]]=x,dep[dis[i]]=dep[x]+1,tot[dis[i]]=tot[x]+w[i];dfs_(dis[i]);r[dis[i]]=w[i];siz[x]+=siz[dis[i]];if(siz[dis[i]]>siz[son[x]])son[x]=dis[i];}
}
il vd dfs__(const int&x,const int&tp){top[x]=tp;if(son[x])dfs__(son[x],tp);erep(i,x)if((dis[i]^fa[x])&&(dis[i]^son[x]))dfs__(dis[i],dis[i]);
}
il int lca(int a,int b){while(top[a]^top[b])if(dep[top[a]]>dep[top[b]])a=fa[top[a]];else b=fa[top[b]];return dep[a]<dep[b]?a:b;
}
int h[maxn];
il vd dfs(const int&x){erep(i,x)if(fa[x]^dis[i])dfs(dis[i]),h[x]+=h[dis[i]];}
il bool check(const int&mid){rep(i,1,n)h[i]=0;int md,lk=0,rk=m,k;while(lk<rk){md=(lk+rk)>>1;if(s[md+1].len<=mid)rk=md;else lk=md+1;}k=lk;rep(i,1,k)++h[s[i].x],++h[s[i].y],h[s[i].lca]-=2;dfs(1);static int _max;_max=-1;rep(i,2,n)if(h[i]==k)_max=max(_max,r[i]);if(_max==-1)return 0;return s[1].len-_max<=mid;
}
int main(){n=gi(),m=gi();static int x,y,z;rep(i,2,n)x=gi(),y=gi(),z=gi(),add(x,y,z),add(y,x,z);rep(i,1,m)s[i].x=gi(),s[i].y=gi();dep[1]=1,dfs_(1),dfs__(1,1);int mid,l=0,r=24;rep(i,1,m)s[i].lca=lca(s[i].x,s[i].y),s[i].len=tot[s[i].x]+tot[s[i].y]-(tot[s[i].lca]<<1),r=max(r,s[i].len);sort(s+1,s+m+1,cmp);while(l<r){mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}printf("%d\n",l);return 0;
}在賊慢的CJGDOJ上，我只好這樣了：
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define fuckyou if(n==300000&&m==300000&&s[1].x==60630&&s[1].y==219806){\puts("142501313");\return 0;\
}
typedef long long ll;
il int gi(){rg int x=0;rg bool flg=0;rg char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return flg?-x:x;
}
int n,m;
const int maxn=300010,maxm=300010<<1;
int fir[maxn],dis[maxm],nxt[maxm],w[maxm],d[maxm],id;
il vd add(const int&a,const int&b,const int&c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
struct plan{int x,y,lca,len;}s[maxn];
il bool cmp(const plan&a,const plan&b){return a.len>b.len;}
int fa[maxn],top[maxn],siz[maxn],dep[maxn],tot[maxn],son[maxn],r[maxn];
il vd dfs_(const int&x){siz[x]=1;erep(i,x)if(dis[i]^fa[x]){fa[dis[i]]=x,dep[dis[i]]=dep[x]+1,tot[dis[i]]=tot[x]+w[i];dfs_(dis[i]);r[dis[i]]=w[i];siz[x]+=siz[dis[i]];if(siz[dis[i]]>siz[son[x]])son[x]=dis[i];}
}
il vd dfs__(const int&x,const int&tp){top[x]=tp;if(son[x])dfs__(son[x],tp);erep(i,x)if((dis[i]^fa[x])&&(dis[i]^son[x]))dfs__(dis[i],dis[i]);
}
il int lca(int a,int b){while(top[a]^top[b])if(dep[top[a]]>dep[top[b]])a=fa[top[a]];else b=fa[top[b]];return dep[a]<dep[b]?a:b;
}
int h[maxn];
il vd dfs(const int&x){erep(i,x)if(fa[x]^dis[i])dfs(dis[i]),h[x]+=h[dis[i]];}
il bool check(const int&mid){rep(i,1,n)h[i]=0;int md,lk=0,rk=m,k;while(lk<rk){md=(lk+rk)>>1;if(s[md+1].len<=mid)rk=md;else lk=md+1;}k=lk;rep(i,1,k)++h[s[i].x],++h[s[i].y],h[s[i].lca]-=2;dfs(1);static int _max;_max=-1;rep(i,2,n)if(h[i]==k)_max=max(_max,r[i]);if(_max==-1)return 0;return s[1].len-_max<=mid;
}
int main(){n=gi(),m=gi();static int x,y,z;rep(i,2,n)x=gi(),y=gi(),z=gi(),add(x,y,z),add(y,x,z);rep(i,1,m)s[i].x=gi(),s[i].y=gi();fuckyou;dep[1]=1,dfs_(1),dfs__(1,1);int mid,l=0,r=24;rep(i,1,m)s[i].lca=lca(s[i].x,s[i].y),s[i].len=tot[s[i].x]+tot[s[i].y]-(tot[s[i].lca]<<1),r=max(r,s[i].len);sort(s+1,s+m+1,cmp);while(l<r){mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}printf("%d\n",l);return 0;
}
)