AT_past202010_m 过不了样例2 求助,玄关
  • 板块灌水区
  • 楼主hzx222
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 20:36
  • 上次更新2024/8/20 21:23:52
查看原帖
AT_past202010_m 过不了样例2 求助,玄关
788765
hzx222楼主2024/8/20 20:36
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m,siz[N],head[N],top[N],rev[N],son[N],dfn[N],fa[N],dep[N];
struct node{
	int next,to;
}ed[N<<1];
int tot,idx;
inline void add(int x,int y){
	ed[++tot].next=head[x];
	ed[tot].to=y;
	head[x]=tot;
}
struct qwq{
	int fi,se;
}a[N<<1];
inline void dfs1(int u,int f){
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	for(int i=head[u];i;i=ed[i].next){
		int v=ed[i].to;
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
inline void dfs2(int x,int vt){
	top[x]=vt;
	dfn[x]=++idx;
	if(son[x])dfs2(son[x],vt);
	for(int i=head[x];i;i=ed[i].next){
		int v=ed[i].to;
		if(v==fa[x]||v==son[x])continue;
		dfs2(v,v);
	}
}
struct tree{
	int l,r,w,lz;
}tr[N<<2];
inline void build(int rt,int l,int r){
	tr[rt].l=l,tr[rt].r=r;
	if(l==r){
		tr[rt].w=0;
		tr[rt].lz=-1;
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
inline void pushdown(int rt){
	if(tr[rt].lz==-1)return;
//	if(rt==25)cout<<"Ppppppppppppppppppp";
	tr[rt<<1].lz=tr[rt<<1|1].lz=tr[rt<<1].w=tr[rt<<1|1].w=tr[rt].lz;
//	if((rt<<1)==25||(rt<<1|1)==25)cout<<"ppppppppppppp";
	tr[rt].lz=-1;
}
inline void change(int rt,int l,int r,int k){
	if(l<=tr[rt].l&&tr[rt].r<=r){
	//	if(rt==25)cout<<"ppppppppppp";
		tr[rt].w=tr[rt].lz=k;
		return;
	}
	pushdown(rt);
	int mid=tr[rt].l+tr[rt].r>>1;
	if(l<=mid)change(rt<<1,l,r,k);
	if(r>mid)change(rt<<1|1,l,r,k);
}
inline int query(int rt,int x){
	if(tr[rt].l==tr[rt].r){
	//	cout<<"aaa"<<tr[rt].w<<" "<<endl;
		return tr[rt].w;
	}
	pushdown(rt);
	int mid=tr[rt].l+tr[rt].r>>1;
	if(x<=mid)return query(rt<<1,x);
	if(x>mid)return query(rt<<1|1,x);
}
inline void lca_change(int x,int y,int val){
	if(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		//cout<<"qwq"<<dfn[top[x]]<<" "<<dfn[x]<<endl;
		change(1,dfn[top[x]],dfn[x],val);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	change(1,dfn[x]+1,dfn[y],val);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i=-~i){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
		a[i].fi=x,a[i].se=y;
	}
	dfs1(1,0),dfs2(1,1),build(1,1,n);
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		lca_change(x,y,z);
	}
	for(int i=1;i<n;i=-~i){
		if(dep[a[i].fi]>dep[a[i].se])swap(a[i].fi,a[i].se);
//		if(a[i].fi==10||a[i].se==10)cout<<"qwq"<<a[i].se;
		printf("%d\n",query(1,dfn[a[i].se]));
	}
} 
2024/8/20 20:36
加载中...