记录编号	593754	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Open18 Platinum]Disruption	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	2.395 s
提交时间	2024-09-11 01:51:55	内存使用	11.57 MiB

#include<bits/stdc++.h>
using namespace std;
int n,k,m,ans,f[50010],d[50010],lj[50010][2],he[100010],cnt=1,p[100010][21];
map<pair<int,int>,int>v1;
inline long long read(){
    long long x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f; 
}
struct node{
	int x;
	int y;
	int z;
}e[100010];
struct node1{
    int v,next;
}s[100010];
void add(int u,int v)
{
    s[cnt].v=v;
    s[cnt].next=he[u];
    he[u]=cnt++;
}        
bool cmp(node A,node B){
	return A.z<B.z;
}
int find(int x){
	if(f[x]==x)
	return x;
	return f[x]=find(f[x]);
}
void join(int x,int y){
	int rx=find(x),ry=find(y);
	f[ry]=rx;
}               
void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    p[u][0]=fa;
    for(int i=1;(1<<i)<=d[u];i++)
        p[u][i]=p[p[u][i-1]][i-1];
    for(int i=he[u];i!=-1;i=s[i].next)
    {
        int v=s[i].v;
        if(v!=fa)
            dfs(v,u);
    }
}                                    
int lca(int a,int b)                                          
{
    if(d[a]>d[b])
        swap(a,b);           
    for(int i=20;i>=0;i--)
        if(d[a]<=d[b]-(1<<i))
            b=p[b][i];            
    if(a==b)
        return a;                
    for(int i=20;i>=0;i--)
    {
        if(p[a][i]==p[b][i])
            continue;
        else
            a=p[a][i],b=p[b][i];           
    }
    return p[a][0];              
}
int main(){
	 freopen("disrupt.in","r",stdin);
    freopen("disrupt.out","w",stdout);
     memset(he,-1,sizeof(he));
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y;
		x=read(),y=read();
		add(x,y);
		add(y,x);
		lj[i][0]=x,lj[i][1]=y;
		f[i]=i;
	}
	f[n]=n;
	dfs(1,0);
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].z;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=find(e[i].x),y=find(e[i].y);
		int zx=lca(x,y);
		while(d[x]>d[zx]){
		    v1[make_pair(p[x][0],x)]=e[i].z;
		    v1[make_pair(x,p[x][0])]=e[i].z;
			f[x]=find(p[x][0]);
			x=find(x);
		}
		while(d[y]>d[zx]){
			v1[make_pair(p[y][0],y)]=e[i].z;
			v1[make_pair(y,p[y][0])]=e[i].z;
			f[y]=find(p[y][0]);
			y=find(y);
		}
	}
	for(int i=1;i<=n-1;i++){
if(v1[make_pair(lj[i][0],lj[i][1])]==0)
		cout<<"-1"<<endl;
		else
		cout<<v1[make_pair(lj[i][0],lj[i][1])]<<endl;
	}
	return 0;
}