[文章目录]
Description
公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？（n,m<=300'000）
我，，，蒟蒻啊。。。
看到数据就想到应该是n*log(n)或是m的。。。然后就各种想，并没有想到二分答案。所以说还是。。。需要加油啊
那个将询问sort的过程可以直接改成O（m）扫，会快很多。不改的话，虽然理论上少扫了几个点，但是mlog（m）的排序还是很浪费时间的。
想法就是先将每个询问的链的长度搞出来，然后二分答案，对于每一个答案，把询问中链长比二分答案大的链在树上差分，以便在O(n)的时间将每条边都被那几条链通过了弄出来。然后在找一条边使得每条链都经过，并且使得每条链的长度都小于二分出的答案。
二分答案？？？我为什么没有想到。。。天啊。。。啊啊啊啊啊
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 310000
int n,m,now,mxx,head[N],nxt[N<<1],to[N<<1],data[N<<1],cnt,k1,k2,deep[N],fa[N][20],mx,dis[N],num[N],ti[N],goal,ans,target;
int read()
{
int re=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
struct node
{
int v1,v2,anc,data;
}a[N];
void add(int x,int y,int z)
{
to[++cnt]=y;
data[cnt]=z;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs(int x)
{
int pre=fa[x][0];
deep[x]=deep[pre]+1;
for(int y,i=head[x];i;i=nxt[i])
{
y=to[i];
if(y!=pre) fa[y][0]=x,dis[y]=dis[x]+data[i],dfs(y);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
int tmp=deep[x]-deep[y];
for(int i=0;(1<<i)<=tmp;i++)
if(tmp&(1<<i)) x=fa[x][i];
if(x==y)return x;
for(int i=mx;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
bool cmp(node x,node y)
{
return x.data<y.data;
}
void dfs_num(int x)
{
int pre=fa[x][0];
for(int y,i=head[x];i;i=nxt[i])
{
y=to[i];
if(y!=pre) dfs_num(y), ti[x]+=ti[y];
}
ti[x]+=num[x];
if(ti[x]==goal) target=max(target,dis[x]-dis[fa[x][0]]);
}
bool check(int x,int tar)
{
if(x<now)
for(int i=x;i<now;i++)
num[a[i].v1]++,num[a[i].v2]++,num[a[i].anc]-=2;
else
for(int i=now;i<x;i++)
num[a[i].v1]--,num[a[i].v2]--,num[a[i].anc]+=2;
now=x;
goal=m-x+1;
memset(ti,0,sizeof(ti));
target=0;
dfs_num(1);
return mxx-target<=tar;
}
bool ok(int x)
{
int mid,l=1,r=m+1,re;
while(l<r)
{
mid=l+r>>1;
if(a[mid].data>x) re=mid,r=mid;
else l=mid+1;
}
return check(re,x);
}
int main()
{
n=read();m=read(); now=m+1;
for(int x,y,z,i=1;i<n;i++)
{
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
deep[1]=1;dfs(1);
for(;(1<<mx)<=n;mx++);
for(int i=1;i<=mx;i++)
for(int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=m;i++)
{
a[i].v1=read(),a[i].v2=read();
a[i].anc=lca(a[i].v1,a[i].v2);
a[i].data=dis[a[i].v1]+dis[a[i].v2]-(dis[a[i].anc]<<1);
}
sort(a+1,a+m+1,cmp);
a[0].data=1<<30;
//for(int i=1;i<=m;i++)
// printf("%d: v %d v %d anc %d dis %d\n",i,a[i].v1,a[i].v2,a[i].anc,a[i].data);
mxx=a[m].data;
int l=0,r=mxx+1;
while(l<r)
{
int mid=l+r>>1;
if(ok(mid)) ans=mid,r=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}