求助,线段树合并模版,60pts,大数据RE
  • 板块学术版
  • 楼主xwh_Marvelous
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/2/11 16:35
  • 上次更新2023/10/24 01:07:25
查看原帖
求助,线段树合并模版,60pts,大数据RE
614527
xwh_Marvelous楼主2023/2/11 16:35
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
int ans[100005]; 
vector<int>mp[100005];
struct LCA{
	int f[100005][50],d[100005];
	void init(int x,int fa){
		f[x][0]=fa;
		d[x]=d[fa]+1;
		for(int i=1;i<=30;i++)f[x][i]=f[f[x][i-1]][i-1];
		for(int i:mp[x]){
			if(i==fa)continue;
			init(i,x); 
		}
	}
	int lca(int a,int b){
		if(d[a]<d[b])swap(a,b);
		for(int i=30;i>=0&&d[a]>d[b];i--){
			if(d[f[a][i]]<d[b])continue;
			a=f[a][i];
		}
		if(a==b)return a;
		for(int i=30;i>=0;i--){
			if(f[a][i]==f[b][i])continue;
			a=f[a][i],b=f[b][i];
		}
		return f[a][0];
	}
}qwq;
struct Segment{
	#define mid ((l+r)>>1)
	#define lson lc[x]
	#define rson rc[x]
	#define pii pair<int,int> 
	#define inf {0,0}
	pii data[1600005];
	int lc[1600005],rc[1600005],tot;
	void addnode(int &x){if(x==0)x=++tot;}
	void push_up(int &x){
		data[x]=inf;
		if(lson)data[x]=data[lson];
		if(rson)data[x]=min(data[x],data[rson]);
	}
	void upd(int op,int p,int &x,int l,int r){
		if(x==-1)return;
		addnode(x);
//		cout<<x<<' '<<l<<' '<<r<<endl; 
		if(l==r){
			data[x]={data[x].first-op,l};
			return;
		}
		if(p<=mid)upd(op,p,lson,l,mid);
		else upd(op,p,rson,mid+1,r);
		push_up(x);
	}
	int qurey(int &x){return data[x].second;}
	void merge(int &a,int &b,int l,int r){
		if(!a){a=b;return;}
		if(!b){return;}
		if(l==r){
			data[a].first+=data[b].first;
			return;
		}
		merge(lc[a],lc[b],l,mid);
		merge(rc[a],rc[b],mid+1,r);
		push_up(a);
	}
	void testify(int &x,int l,int r){
		if(x==0)return;
		if(l==r){
			cout<<data[x].second<<' '<<-data[x].first<<endl;
		}
		testify(lson,l,mid);
		testify(rson,mid+1,r);
	}
}hitoi;
int root[100005];
void dfs(int x,int f){
	for(int i:mp[x]){
		if(i==f)continue;
		dfs(i,x);
		hitoi.merge(root[x],root[i],0,100000); 
	}
//	cout<<x<<endl;
//	hitoi.testify(root[x],0,100000);
	ans[x]=hitoi.qurey(root[x]);
}
int main(){
//	freopen("exam.in","r",stdin);
//	freopen("exam.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	qwq.init(1,0);
	root[0]=-1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
//		cout<<x<<endl;
		hitoi.upd(1,z,root[x],0,100000);
//		cout<<endl<<y<<endl;
		hitoi.upd(1,z,root[y],0,100000);
//		cout<<endl<<qwq.lca(x,y)<<endl;
		hitoi.upd(-1,z,root[qwq.lca(x,y)],0,100000);
//		cout<<endl<<qwq.f[qwq.lca(x,y)][0]<<endl;
		hitoi.upd(-1,z,root[qwq.f[qwq.lca(x,y)][0]],0,100000);
//		cout<<endl;
	}
//	cout<<hitoi.qurey(root[1])<<endl;
	for(int i=1;i<=n;i++){
		hitoi.upd(0,0,root[i],0,100000);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

谢谢,qwq;

2023/2/11 16:35
加载中...