台风防范

题目描述

由于频繁有台风登陆，A 国如今受到狂风暴雨的洗礼。在这种恶劣的环境中，保证交通畅通是 A 国王首要关心的事情。A 国当前的交通情况是由 $N-1$ 条双向道路将 $N$ 个城市联通起来，其中每条道路的长度都是 $1$。需要注意，任意两个城市都是可以互相到达的。

A 国王为了应对某条道路阻断后带来的不好的结果，他决定启用备用道路，现在一共有 $M$ 条备用的双向道路，每一条的长度均为一个至多为 $10^9$ 的正整数。人们仍然可以使用未被阻断的原有道路进行移动。

如果某条原有的道路被阻断了，整个国家就会被分为两块不相交的区域，那么 A 国王就会从额外修建的道路中选择一条能够使这两块区域连通的，取代被阻断的那条，从而使得整个国家重新联通起来。

对于 A 国的每一条原有的道路，帮助 A 国王选出最短的替代用的道路。

输入格式

输入的第一行包含 $N$ 和 $M$。

接下来的 $N−1$ 行，每行用整数 $p$ 和 $q$ 描述了一条原有的道路，其中 $p,q$ 是这条道路连接的两个城市。

剩下的 $M$ 行，每行用三个整数 $p,q$ 和 $r$ 描述了一条额外的道路，其中 $r$ 是这条道路的长度。

输出格式

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

样例 1

样例输入 1

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

样例输出 1

7
7
8
5
5

提示

对于 $20\%$ 的数据，$2\le N\le 5\times10^3,1\le M\le 1\times10^4$。

对于额外 $20\%$ 的数据，原来所有城市道路构成一条链。

对于 $100\%$ 的数据，$2\le N\le 5\times 10^4,1\le M\le 5\times 10^4,1\le p,q\le N,p \neq q, 0 \le r \le 10^9$。

代码

#include<bits/stdc++.h>
#define lson o<<1
#define rson o<<1|1
#define nmid int mid=(nowr+nowl)>>1;
//#include<ctime>
//#include<windows.h>
using namespace std;
const int maxn=5e4+5;
int n,m;
struct Edge{
	int _this,nxt;
	Edge(){
		_this=nxt=0;
	}
}edge[maxn<<1];
int headnxt[maxn];
int idx;
void merge(int from,int to){
	edge[++idx]._this=to;
	edge[idx].nxt=headnxt[from];
	headnxt[from]=idx;
}
bool vis[maxn];
int fa[maxn],deep[maxn],root[maxn];
int id[maxn];
int tim=1;
void dfs(int f){
	int maxson=-1;
	for(int it=headnxt[f];it;it=edge[it].nxt){
		if(!vis[edge[it]._this]&&edge[it]._this>maxson)
			maxson=edge[it]._this;
	}
	for(int it=headnxt[f];it;it=edge[it].nxt){
		int nowtry=edge[it]._this;
		if(!vis[nowtry]){
			++tim;
			id[nowtry]=tim;
			vis[nowtry]=1;
			fa[id[nowtry]]=id[f];
			deep[id[nowtry]]=deep[id[f]]+1;
			if(nowtry==maxson){
				root[id[nowtry]]=root[id[f]];
			}
			else root[id[nowtry]]=id[nowtry];
			dfs(nowtry);
		}
	}
}

struct Normedge{
	int s,t,w;
}helpedge[maxn],reqedge[maxn];
bool cmp(Normedge x,Normedge y){return x.w>y.w;}

int t[maxn<<2];
//void push_up(int o){
//	t[o]=min(t[lson],t[rson]);
//}
//void build(int nowl,int nowr,int o){
//	if(nowl==nowr){
//		t[o]=0x3f3f3f3f;
//	}
//	nmid;
//	build(nowl,mid,lson)	
//	build(mid+1,nowr,rson);
//}
void push_down(int o){
	if(t[o]==-1) return;
	t[lson]=t[o];
	t[rson]=t[o];
	t[o]=-1;
}
int query(int nowl,int nowr,int o,int p){
	if(nowl==nowr){
		return t[o];
	}
	nmid;
	push_down(o);
	int res=0;
	if(p<=mid) res=query(nowl,mid,lson,p);
	else res=query(mid+1,nowr,rson,p);
	return res;
}
void update(int nowl,int nowr,int l,int r,int o,int val){
	if(l<=nowl&&nowr<=r){
		t[o]=val;
		return;
	}
	nmid;
	push_down(o);
	if(l<=mid) update(nowl,mid,l,r,lson,val);
	if(r>mid) update(mid+1,nowr,l,r,rson,val);
//	push_up(o);
}
int main(){
//	freopen("typhoon.in","r",stdin);
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);


	scanf("%d%d",&n,&m);
	for(int i=1;i<n;++i){
		scanf("%d%d",&reqedge[i].s,&reqedge[i].t);
		merge(reqedge[i].s,reqedge[i].t);
		merge(reqedge[i].t,reqedge[i].s);
	}
	
	
	id[1]=1;
	fa[id[1]]=-1;
	deep[id[1]]=1;
	root[id[1]]=id[1];
	vis[1]=1;
	dfs(1);//求id（dfn）
	
	
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&helpedge[i].s,&helpedge[i].t,&helpedge[i].w);
	}
	sort(helpedge+1,helpedge+m+1,cmp);
	//插入辅助边
	
//	DWORD start=GetTickCount(),end;
	memset(t,-1,sizeof t);
	for(int i=1;i<=m;++i){
		int s=helpedge[i].s,e=helpedge[i].t,w=helpedge[i].w;
		s=id[s];
		e=id[e];
		
		while(root[s]!=root[e]){
			if(deep[root[s]]>deep[root[e]]){
				update(1,n,root[s],s,1,w);
//				cout<<query(1,n,1,5);
				s=fa[root[s]];
			}
			else{
				update(1,n,root[e],e,1,w);
				e=fa[root[e]];
			}
		}
		if(s>e){
			update(1,n,e+1,s,1,w);
		}
		else{
			update(1,n,s+1,e,1,w);
		}	
//		end=GetTickCount();
//		cout<<"t:"<<end-start<<endl;
//		start=GetTickCount();
	}
	
	
	for(int i=1;i<n;++i){
		int s=reqedge[i].s,e=reqedge[i].t;
		s=id[s];
		e=id[e];
		if(fa[e]==s) swap(e,s);
		int ans=query(1,n,1,s);
		printf("%d\n",ans);
	}
    return 0;
}

树链剖分+线段覆盖+线段树维护

30pts wa on #1,2,9

tle on #4,7,8,10