P2680 运输计划
首先看到最大的最小要想到二分
之后考虑check..
我们将道路长度>mid的标记,找出被所有道路标记的边,去掉其中最大的,之后再和mid比较即可.
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<bits/stdc++.h> #define ll long long #define max(a,b) a>b?a:b #define re register using namespace std; const int N=3e5+10; int n,m,link[N],tot,d[N],c[N],cnt,ans,f[N][25],deep[N],dire[N]; struct edge{int y,v,next;}a[N<<1]; struct data{int x,y,v;}b[N]; vector<int>v; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,ff=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getc();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getc();} return x*ff; } inline void add(int x,int y,int v) { a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].v=v;a[tot].next=link[y];link[y]=tot; } inline void bfs() { queue<int>q;q.push(1); memset(deep,0,sizeof(deep)); deep[1]=1; while(!q.empty()) { int x=q.front();q.pop(); for(re int i=link[x];i;i=a[i].next) { int y=a[i].y; if(deep[y]) continue; dire[y]=i; deep[y]=deep[x]+1; q.push(y); f[y][0]=x; for(re int j=1;j<21;++j) f[y][j]=f[f[y][j-1]][j-1]; } } } inline int lca(int a,int b) { if(deep[a]>deep[b]) swap(a,b); for(re int i=20;i>-1;--i) if(deep[f[b][i]]>=deep[a]) b=f[b][i]; if(a==b) return a; for(re int i=20;i>-1;--i) if(f[b][i]!=f[a][i]) a=f[a][i],b=f[b][i]; return f[a][0]; } inline void dfs(int x) { for(re int i=link[x];i;i=a[i].next) { int y=a[i].y; if(y==f[x][0]) continue; d[y]=d[x]+a[i].v; dfs(y); } } inline void dfs1(int x) { for(re int i=link[x];i;i=a[i].next) { int y=a[i].y; if(y==f[x][0]) continue; dfs1(y); c[x]+=c[y]; } if(c[x]==cnt) ans=max(ans,a[dire[x]].v); } inline bool check(int mid) { cnt=0;v.clear(); memset(c,0,sizeof(c)); for(re int i=1;i<m+1;++i) { if(b[i].v>mid) { cnt++; c[b[i].x]++; c[b[i].y]++; c[lca(b[i].x,b[i].y)]-=2; v.push_back(i); } } if(!cnt) return true; ans=0;dfs1(1); if(!ans) return false; int len=v.size(); for(int i=0;i<len;++i) if(b[v[i]].v-ans>mid) return false; return true; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(re int i=1;i<n;++i) { int x=read(),y=read(),v=read(); add(x,y,v); } bfs();dfs(1); for(re int i=1;i<m+1;++i) { b[i].x=read(); b[i].y=read(); b[i].v=d[b[i].x]+d[b[i].y]-2*d[lca(b[i].x,b[i].y)]; } int l=0,r=0; for(re int i=1;i<n+1;++i) r=max(r,d[i]); r*=2; while(l<r) { int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d",l); return 0; }