萌新15pts求助模板题
查看原帖
萌新15pts求助模板题
890311
xiaoyang111楼主2024/6/23 16:52
#include <iostream>
#include <vector>
using namespace std;
const int N=1e5+5,M=(N+5)*100;
struct Tree{
	int ls,rs;
	int mx,id;//最大的数和最大的数在哪里
	Tree()=default;
	Tree(int ls,int rs,int mx,int id) : ls(ls),rs(rs),mx(mx),id(id) {} 
}tree[M];
void pushup(int u){
	int l=tree[u].ls,r=tree[u].rs;
	if (tree[l].mx>tree[r].mx || 
	tree[l].mx==tree[r].mx && tree[l].id<tree[r].id){
		tree[u].mx=tree[l].mx;
		tree[u].id=tree[l].id;
//		cout<<tree[u].mx<<" "<<tree[u].id<<" "<<u<<" | ";
	}else{
		tree[u].mx=tree[r].mx;
		tree[u].id=tree[r].id;
	}
}
void upd(int u,int num){
	tree[u].mx+=num;//直接加 
}
int tot;
void modify(int &u,int l,int r,int i,int num){
	if (u==0){
		u=++tot;
		tree[tot]=(Tree){0,0,0,0};
	}
	if (l>=i && r<=i){
		upd(u,num);
		tree[u].id=i;
//		cout<<u<<" "<<l<<" "<<r<<" "<<num<<endl;
		return;
	}
	if (r<i || l>i){
		return;
	}
	int mid=l+r>>1;
	modify(tree[u].ls,l,mid,i,num);
	modify(tree[u].rs,mid+1,r,i,num);
	pushup(u);
}
int root[N];//每个点的根节点是什么 
int query(int i){
	return tree[root[i]].id;
}
int f[N][31],l[N];
int n,m;
vector<int> g[N];
void dfs(int u,int fa){
	f[u][0]=fa;
	l[u]=l[fa]+1;
	for (const auto &item : g[u]){
		if (item==fa){
			continue;
		}
		dfs(item,u);
	}
}
int merge(int u,int v,int l,int r){
	if (u==0 || v==0){//不用往下遍历了 
		return u|v;
	}
	if (l==r){//合并信息 
		tree[u].mx+=tree[v].mx;//直接加
		return u; 
	}
	int mid=l+r>>1;
	tree[u].ls=merge(tree[u].ls,tree[v].ls,l,mid);
	tree[u].rs=merge(tree[u].rs,tree[v].rs,l,mid);
	pushup(u);
	return u;
}
int lca(int u,int v){
	if (l[u]<l[v]){
		swap(u,v);
	}
	int t=l[u]-l[v];
	for (int i=30;i>=0;--i){
		if (t>>i&1){
			u=f[u][i];
		}
	}
	if (u==v){
		return u;
	}
	for (int i=30;i>=0;--i){
		if (f[u][i]!=f[v][i]){
			u=f[u][i];
			v=f[v][i];
		}
	}
	return f[u][0];
}
void dfs2(int u,int fa){
	for (const auto &item : g[u]){
		if (item==fa){
			continue;
		}
		dfs2(item,u);
		root[u]=merge(root[u],root[item],1,N-1);
	}
}
int main(){
	cin >> n >> m;
	int u,v;
	for (int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		g[v].emplace_back(u);
		g[u].emplace_back(v);
	}
	dfs(1,0);
	for (int i=1;i<31;++i){
		for (int j=1;j<=n;++j){
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	int w;
	for (int _=0;_<m;++_){
		scanf("%d%d%d",&u,&v,&w);
		int t=lca(u,v);
//		cout<<"Qwqaqwqaq"<<t<<endl;
		modify(root[u],1,N,w,1);
		modify(root[v],1,N,w,1);
		modify(root[t],1,N,w,-1);
		if (f[t][0]==0) continue;
		modify(root[f[t][0]],1,N,w,-1);
	}
//	for (int i=1;i<=n;++i) cout<<root[i]<<" ";
//	cout<<endl;
	dfs2(1,0);
	for (int i=1;i<=n;++i){
		printf("%d\n",query(i));
	}
	return 0;
}
2024/6/23 16:52
加载中...