50pts其余全WA求调
查看原帖
50pts其余全WA求调
783170
liaiyang楼主2023/10/22 11:05

rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define y1 Y1
#define debug(...) fprintf(stderr,__VA_ARGS__)
// #define min(a,b) (a<b?a:b) 
// #define max(a,b) (a>b?a:b)
#define P pair<int,int>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod) 
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
mt19937 rnd(time(0));
inline int read(int u=0, char c=getchar(), bool f=false){
	for (;!isdigit(c);c=getchar()) f|=c=='-';
	for (;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+c-'0';
	return f?-u:u;
}
inline void wt(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) wt(x/10);
	putchar(x%10+48);
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1; 
const int mod=998244353,g=3,gi=332748118;
const int N=1e5+10;
struct Tree{
	struct node{
		int lc,rc,sum,id;
	}tr[60*N];
	int cnt,root[N];
	void pushup(int now){
		if(tr[tr[now].lc].sum>=tr[tr[now].rc].sum) 
			tr[now].sum=tr[tr[now].lc].sum,tr[now].id=tr[tr[now].lc].id;
		else tr[now].sum=tr[tr[now].rc].sum,tr[now].id=tr[tr[now].rc].id;
	}
	void merge(int &x,int &y,int l,int r){
		if(!x||!y) return x+=y,void();
		if(l==r) return tr[x].sum+=tr[y].sum,tr[x].id=l,void();
		int mid=l+r>>1;
		merge(tr[x].lc,tr[y].lc,l,mid);
		merge(tr[x].rc,tr[y].rc,mid+1,r);
		pushup(x);
	}
	void modify(int &now,int l,int r,int pos,int x){
		if(!now) now=++cnt;
		if(l==r) return tr[now].sum+=x,tr[now].id=l,void();
		int mid=l+r>>1;
		if(pos<=mid) modify(tr[now].lc,l,mid,pos,x);
		else modify(tr[now].rc,mid+1,r,pos,x);
		pushup(now);
	}
}T;
int n,m,dfn[N<<1],id[N],dep[N],cnt,f[N<<1][30],fa[N];
vector<int>e[N];
void dfs(int x,int fath){
	dfn[++cnt]=x,id[x]=cnt,dep[x]=dep[fath]+1,fa[x]=fath;
	for(int i:e[x]) if(i!=fath) dfs(i,x),dfn[++cnt]=x;
}
int lca(int x,int y){
	x=id[x],y=id[y];
	if(x>y) swap(x,y);
	int k=log2(y-x+1);
	return (dep[f[x][k]]<dep[f[y-(1<<k)+1][k]]?f[x][k]:f[y-(1<<k)+1][k]);
}
void dfs1(int x,int fa){
	for(int i:e[x]) if(i!=fa) dfs1(i,x),T.merge(T.root[x],T.root[i],1,1e5);
}
main(){
	n=rd;m=rd;
	for(int i=1;i<n;i++){
		int x=rd,y=rd;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=cnt;i++) f[i][0]=dfn[i];
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)<=cnt;i++)
			f[i][j]=(dep[f[i][j-1]]<dep[f[i+(1<<j-1)][j-1]]?f[i][j-1]:f[i+(1<<j-1)][j-1]);
	for(int i=1;i<=m;i++){
		int x=rd,y=rd,z=rd;
		T.modify(T.root[x],1,1e5,z,1),T.modify(T.root[y],1,1e5,z,1);
		T.modify(T.root[lca(x,y)],1,1e5,z,-1),T.modify(T.root[fa[lca(x,y)]],1,1e5,z,-1);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++) wt(T.tr[T.root[i]].sum?T.tr[T.root[i]].id:0,'\n');
	return 0;
}
2023/10/22 11:05
加载中...