寒假作业是刷完05年到15年的NOIP题。。
当然本来是想的话可以做HNOI的 看了看难度还是算了=-=
于是趁机来填NOIP2015的坑
这道题嘛。。就是首先二分答案。。
然后把长度大于这个答案的运输计划取个交集,找到这个交集里最大的边
然后用距离最长的运输计划-这条边,判断一下和二分出的答案的大小=-=
【听上去还是很容易的是吧?
然后关键就是怎么取交
这里可以用一下差分。。修改O(1) 之后全部扫一遍
【太神了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
// <transport.cpp> - 02/07/16 12:23:52 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=300002; int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],dis[MAXN],tf[MAXN],btf[MAXN]; int n,m,tot,maxl; vector <pair<int,int> >b[MAXN]; struct PLAN{ int a,b,v; bool operator <(PLAN b) const{return v<b.v;} bool operator >(PLAN b) const{return v>b.v;} }plan[MAXN]; void dfs1(int x){ siz[x]=1;son[x]=0; for(int i=0;i<b[x].size();i++){ int next=b[x][i].first; if(next==f[x])continue; dep[next]=dep[x]+1; tf[next]=b[x][i].second; dis[next]=dis[x]+tf[next]; f[next]=x; dfs1(next); siz[x]+=siz[next]; if(!son[x]||siz[son[x]]<siz[next])son[x]=next; } } void dfs2(int x,int y){ w[x]=++tot;top[x]=y;btf[tot]=tf[x]; if(son[x])dfs2(son[x],y); for(int i=0;i<b[x].size();i++){ int next=b[x][i].first; if(next==f[x]||next==son[x])continue; dfs2(b[x][i].first,b[x][i].first); } } int cd[MAXN]; void cf(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); cd[w[top[u]]]++; cd[w[u]+1]--; u=f[top[u]]; } if(dep[u]<dep[v])swap(u,v); cd[w[v]+1]++; cd[w[u]+1]--; } bool check(int x){ int i; for(i=1;i<=m;i++)if(plan[i].v>x)break; int sum=m-i+1; for(int o=1;o<=n;o++)cd[o]=0; for(;i<=m;i++)cf(plan[i].a,plan[i].b); int now=0,ans=0; for(int o=1;o<=n;o++){ now+=cd[o]; if(now==sum)ans=max(ans,btf[o]); } return maxl-ans<=x; } int lca(int u,int v){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); u=f[top[u]]; } if(dep[u]<dep[v])swap(u,v); return v; } int main(){ freopen("transport.in","r",stdin); freopen("transport.out","w",stdout); n=getint(),m=getint(); for(int i=1;i<=n-1;i++){ int u=getint(),v=getint(),w=getint(); b[u].push_back(make_pair(v,w)); b[v].push_back(make_pair(u,w)); } dfs1(1);dfs2(1,1); for(int i=1;i<=m;i++){ plan[i].a=getint(),plan[i].b=getint(); plan[i].v=dis[plan[i].a]+dis[plan[i].b]-(dis[lca(plan[i].a,plan[i].b)]<<1); maxl=max(maxl,plan[i].v); } sort(plan+1,plan+1+m); int l=0,r=maxl; while(l<r){ int m=(l+r)>>1; if(check(m))r=m; else l=m+1; } cout<<l; return 0; } |