[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

我们考虑一下那些额外的双向路对答案的影响，一条双向路能被用上，只有x,y路径上的边断了才能用上，这个就是树链剖分裸题，线段树维护最小值即可

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)	print(x/10);

	putchar(x%10+'0');

}

const int N=5e4;

int ID[N+10],n,m;

struct Segment{

	#define ls (p<<1)

	#define rs (p<<1|1)

	int tree[(N<<2)+10],Lazy[(N<<2)+10];

	Segment(){

		memset(tree,127,sizeof(tree));

		memset(Lazy,127,sizeof(Lazy));

	}

	void Add_Min(int p,int v){

		tree[p]=min(tree[p],v);

		Lazy[p]=min(Lazy[p],v);

	}

	void pushdown(int p){

		if (Lazy[p]==inf)	return;

		Add_Min(ls,Lazy[p]);

		Add_Min(rs,Lazy[p]);

		Lazy[p]=inf;

	}

	void insert(int p,int l,int r,int x,int y,int v){

		if (x<=l&&r<=y){

			Add_Min(p,v);

			return;

		}

		pushdown(p);

		int mid=(l+r)>>1;

		if (x<=mid)	insert(ls,l,mid,x,y,v);

		if (y>mid)	insert(rs,mid+1,r,x,y,v);

		tree[p]=min(tree[ls],tree[rs]);

	}

	int Query(int p,int l,int r,int x){

		if (l==r)	return tree[p];

		pushdown(p);

		int mid=(l+r)>>1;

		if (x<=mid)	return Query(ls,l,mid,x);

		else	return Query(rs,mid+1,r,x);

	}

}T;

struct S1{

	int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],tot,Time;

	int fa[N+10],top[N+10],size[N+10],Rem[N+10],deep[N+10];

	void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}

	void insert(int x,int y){join(x,y),join(y,x);}

	void build(int x){

		deep[x]=deep[fa[x]]+1,size[x]=1;

		for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

			if (son==fa[x])	continue;

			fa[son]=x,build(son);

			size[x]+=size[son];

			if (size[son]>size[Rem[x]])	Rem[x]=son;

		}

	}

	void dfs(int x){

		if (!x)	return;

		ID[x]=++Time;

		top[x]=Rem[fa[x]]==x?top[fa[x]]:x;

		dfs(Rem[x]);

		for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

			if (son==fa[x]||son==Rem[x])	continue;

			dfs(son);

		}

	}

	void work(int x,int y,int z){

		while (top[x]!=top[y]){

			if (deep[top[x]]<deep[top[y]])	swap(x,y);

			T.insert(1,1,n,ID[top[x]],ID[x],z);

			x=fa[top[x]];

		}

		if (x==y)	return;

		if (deep[x]>deep[y])	swap(x,y);

		T.insert(1,1,n,ID[Rem[x]],ID[y],z);

		return;

	}

	void Get_Ans(int x,int y){

		if (deep[x]<deep[y])	swap(x,y);

		int tmp=T.Query(1,1,n,ID[x]);

		printf("%d\n",tmp==inf?-1:tmp);

	}

}Tree;

struct S2{int x,y;}A[N+10];

int main(){

	n=read(),m=read();

	for (int i=1;i<n;i++){

		int x=read(),y=read();

		Tree.insert(x,y);

		A[i]=(S2){x,y};

	}

	Tree.build(1),Tree.dfs(1);

	for (int i=1;i<=m;i++){

		int x=read(),y=read(),z=read();

		Tree.work(x,y,z);

	}

	for (int i=1;i<n;i++)	Tree.Get_Ans(A[i].x,A[i].y);

	return 0;

}

巴特西

[Usaco2018 Open]Disruption

最新文章

热门文章