6pts求助!!!
查看原帖
6pts求助!!!
254491
橙橙like海绵楼主2022/12/18 20:43
#include<bits/stdc++.h>
#define ll long long 
#define int long long 
using namespace std;
const int N=5e5+10;
const int inf=0x3f3f3f3f;
int n,m,a[N],w[N];
int dep[N],son[N],sz[N],top[N],fa[N];
int dfn[N],tot;
int val[N],flag[N];
int h[N],cnt;
struct deno{
	int nxt,to;
}e[N<<2];
struct po{
	ll from,to,val;
}p[N],pp[N];
inline ll read(){
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
void add(int u,int v){
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	h[u]=cnt;
}
void Add(int &x,int v){
	x=(x==-1?v:min(x,v));
}
void push_up(int k){
	if(val[k<<1]==-1) val[k]=val[k<<1|1];
	else if(val[k<<1|1]==-1) val[k]=val[k<<1];
	else val[k]=min(val[k<<1],val[k<<1|1]);
}
void push_down(int k){
	if(flag[k]!=-1){
		Add(val[k],flag[k]);
		Add(flag[k<<1],flag[k]);
		Add(flag[k<<1|1],flag[k]);
		flag[k]=-1;
	}
}
void change(int k,int l,int r,int x,int y,ll v){
	//if(y<l||x>r) return ;
	if(x<=l&&r<=y){
		Add(val[k],v);
		Add(flag[k<<1],v);
		Add(flag[k<<1|1],v);
		return;
	}
	int mid=(l+r)>>1;
	push_down(k);
	if(x<=mid) change(k<<1,l,mid,x,y,v);
	if(mid<y) change(k<<1|1,mid+1,r,x,y,v);
	// change(k<<1,l,mid,x,y,v),change(k<<1|1,mid+1,r,x,y,v);
	push_up(k);
}
ll query(int k,int l,int r,int x){
	if(l==r&&l==x) return val[k];
	int mid=(l+r)>>1;
	push_down(k);
	ll t1=-1,t2=-1;
	if(x<=mid) t1=query(k<<1,l,mid,x);
	else t2=query(k<<1|1,mid+1,r,x);
	if(t1==-1) return t2;
	else if(t2==-1) return t1;
	else return min(t1,t2);
}
void crange(int u,int v,ll k){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		change(1,1,n,dfn[top[u]],dfn[u],k);
		u=fa[top[u]];
	}
	if(u==v) return ;
	if(dep[u]>dep[v]) swap(u,v);
	change(1,1,n,dfn[u]+1,dfn[v],k);
}
void dfs1(int u,int f){
	fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}	
}
void dfs2(int u,int topf){
	top[u]=topf;dfn[u]=++tot;
	if(!son[u]) return ;
	dfs2(son[u],topf);
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==son[u]||v==fa[u]) continue;
		dfs2(v,v);
	}
}
bool cmp(po a,po b){return a.val<b.val;}
signed main(){
	n=read();m=read();
	int u,v,ww;
	for(int i=1;i<n;i++){
		u=read();v=read();
		add(u,v);add(v,u);
		p[i].from=u;p[i].to=v;
	}
	for(int i=1;i<=m;i++){
		u=read();v=read();ww=read();
		pp[i].from=u;pp[i].to=v;pp[i].val=ww;
		//crange(u,v,ww);
	}
	dfs1(1,0);
	dfs2(1,1);
	//for(int i=1;i<=n;i++) printf("%d\n",[i]);
	memset(val,-1,sizeof(val));
	memset(flag,-1,sizeof(flag));
	sort(pp+1,pp+1+m,cmp);
	for(int i=1;i<=m;i++) crange(pp[i].from,pp[i].to,pp[i].val);
	for(int i=1,res;i<n;i++){
		res=query(1,1,n,dep[p[i].from]>dep[p[i].to]?dfn[p[i].from]:dfn[p[i].to]);
		printf("%lld\n",res);
	}
	return 0;
}
2022/12/18 20:43
加载中...