bzoj5279 [Usaco2018 Open]Disruption

bzoj5279 [Usaco2018 Open]Disruption

​​ Description

Farmer John自豪于他所经营的交通发达的的农场。这个农场是由N块牧场（2≤N≤50,000）组成的，N?1条双向道 路将它们连接起来，每一条道路的都为一单位长度。Farmer John注意到，从任何一块牧场到另一块牧场，都能通 过一组合适的道路到达。尽管FJ的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会 将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是FJ又建造了 M条额外的双向道路（1≤M≤50,000），每一条的长度都是一个至多为10^9的正整数。奶牛们仍然可以使用原有的 道路进行移动，除非其中的某些被阻断了。如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那 么FJ就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从 任何一块牧场去往另一块牧场。对于农场上每一条原有的道路，帮助FJ选出最短的替代用的道路。 Input

输入的第一行包含N和M。接下来的N-1行，每行用整数p和q描述了一条原有的道路 其中p≠q是这条道路连接的两块牧场（在1…N范围内）。 剩下的M行，每行用三个整数p、q和r描述了一条额外的道路，其中r是这条道路的长度。 任何两块牧场之间至多只有一条道路。 Output

对原有的N-1条道路的每一条，按照它们在输入中出现的顺序 输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。 如果不存在合适的替代用的道路，输出-1。 Sample Input

6 3 1 2 1 3 4 1 4 5 6 5 2 3 7 3 6 8 6 4 5 Sample Output

7 7 8 5 5 HINT

Source

Platinum

复习下链剖 庆幸的是这么裸的板子能1A 不庆幸的是这题让蒟蒻我思考了很久才会做..

考虑每条边其实就是会对他管辖的两点的这条链上的点断开可以选择我这条边 所以我的影响只是我两边的点的一条链 所以直接边的树剖即可 开心的话愿意lct应该也Okay

#include#include#define lc (x<<1)#define rc (x<<1|1)#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=5e4+10;const int inf=0x3f3f3f3f;struct node{ int y,next,id;}data[N<<1];int h[N],size[N],son[N],fa[N],dep[N],b[N],tp[N],dfn[N],num,mn[N<<2],n,m; inline void dfs(int x){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa[x]) continue;fa[y]=x;b[data[i].id]=y; dep[y]=dep[x]+1;dfs(y);size[x]+=size[y];if (size[y]>size[son[x]]) son[x]=y; }}inline void dfs1(int x,int top){ dfn[x]=++num;tp[x]=top; if (son[x]) dfs1(son[x],top); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa[x]||y==son[x]) continue; dfs1(y,y); }}inline void build(int x,int l,int r){ mn[x]=inf;if (l==r) return;int mid=l+r>>1; build(lc,l,mid);build(rc,mid+1,r);}inline void pushdown(int x){ mn[lc]=min(mn[lc],mn[x]);mn[rc]=min(mn[rc],mn[x]);}inline void modify(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){mn[x]=min(mn[x],v);return;}pushdown(x);int mid=l+r>>1; if (l1<=mid) modify(lc,l,mid,l1,r1,v);if (r1>mid) modify(rc,mid+1,r,l1,r1,v);}inline void dfs(int x,int l,int r){ if (l==r) return;pushdown(x);int mid=l+r>>1; dfs(lc,l,mid);dfs(rc,mid+1,r);}inline int query(int x,int l,int r,int p){ if (l==r) return mn[x];int mid=l+r>>1; if (p<=mid) return query(lc,l,mid,p);else return query(rc,mid+1,r,p);}int main(){ freopen("bzoj5279.in","r",stdin); n=read();m=read(); for (int i=1;idep[y]) swap(x,y);modify(1,1,n,dfn[x]+1,dfn[y],z); }dfs(1,1,n); for (int i=1,id,tmp;i<=nm;i+=2){ id=data[i].id;tmp=query(1,1,n,dfn[b[id]]); printf("%d\n",tmp==inf?-1:tmp); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。