90pts MLE求助
查看原帖
90pts MLE求助
538005
wan_bei_shu楼主2023/5/27 17:22
#include<bits/stdc++.h>
using namespace std;
struct node{
	int l, r, cnt, maxx, num, rs, ls;
};
int tot;
int n, m;
int fa[100010];
node p[4000010];
int ans[100010];
int root[100010];
int deep[100010];
int up[100010][20];
vector<int> v[100010];
void dfs(int x, int f) {
	deep[x] = deep[f] + 1;
	for(int i=0; i<v[x].size(); ++i) {
		int y = v[x][i];
		if(y!=f) {
			fa[y] = x;
			up[y][0] = x;
		 	dfs(y, x);
		}
	}
}
void init_up() {
	for (int j = 1; j < 20; ++j)
    	for (int i = 1; i <= n; ++i)
      		up[i][j] = up[up[i][j - 1]][j - 1];
}
int LCA(int x, int y) {
	if(deep[x]<deep[y]) swap(x, y);
	int now=deep[x]-deep[y];
	while(now>0) {
		int k=log2(now);
		now -= (1<<k);
		x = up[x][k];
	}
	if(x == y) return x;
	int k=log2(deep[x]);
	for(int i=k; i>=0; --i) {
		if(up[x][i] != up[y][i]) x=up[x][i], y=up[y][i];
	}
	return fa[x];
}
void update(int x, int c, int u) {
	int l=p[x].l, r=p[x].r;
	if(l==r) {
		p[x].cnt+=u;
		p[x].maxx=p[x].cnt;
		p[x].num=c;
		return ;
	}
	int mid=(l+r)>>1;
	if(c<=mid) {
		if(!p[x].ls) p[x].ls=++tot, p[tot].l=l, p[tot].r=mid;
		update(p[x].ls, c, u);
	}
	else {
		if(!p[x].rs) p[x].rs=++tot, p[tot].l=mid+1, p[tot].r=r;
		update(p[x].rs, c, u);
	}
	p[x].cnt=p[p[x].ls].cnt + p[p[x].rs].cnt;
	if(p[p[x].ls].maxx>=p[p[x].rs].maxx) p[x].num=p[p[x].ls].num, p[x].maxx=p[p[x].ls].maxx;
	else p[x].num=p[p[x].rs].num, p[x].maxx=p[p[x].rs].maxx;
}
int unset_1(int x, int y, int l, int r) {
	if(!x) return y;
	if(!y) return x;
	if(l==r) {
		p[x].cnt+=p[y].cnt;
		p[x].maxx+=p[y].maxx;
		return x;
	}
	int mid = (l+r)>>1;
	p[x].ls = unset_1(p[x].ls, p[y].ls, l, mid);
	p[x].rs = unset_1(p[x].rs, p[y].rs, mid+1, r);
	p[x].cnt=p[p[x].ls].cnt + p[p[x].rs].cnt;
	if(p[p[x].ls].maxx>=p[p[x].rs].maxx) p[x].num=p[p[x].ls].num, p[x].maxx=p[p[x].ls].maxx;
	else p[x].num=p[p[x].rs].num, p[x].maxx=p[p[x].rs].maxx;
	return x;
}
node unset(int x) {
	for(int i=0; i<v[x].size(); ++i) {
		int y=v[x][i];
		if(y!=fa[x]) {
			unset(y);
			unset_1(x, y, 1, 100000);
		}
	}
	if(p[x].maxx>0) ans[x]=p[x].num;
	return p[x];
}
int main() {
	cin >> n >> m;
	int v1, v2, v3;
	for(int i=1; i<n; ++i) {
		cin >> v1 >> v2;
		v[v1].push_back(v2);
		v[v2].push_back(v1);
		root[i] = ++tot;
		p[tot].l=1, p[tot].r=100000;
	}
	root[n] = ++tot;
	p[tot].l=1, p[tot].r=100000;
	dfs(1, 0);
	init_up();
	for(int i=1; i<=m; ++i) {
		cin >> v1 >> v2 >> v3;
		if(v1 == v2) {
			update(root[v1], v3, 1);
			if(v1!=1) update(fa[root[v1]], v3, -1);
		}
		else {
			int lca=LCA(v1, v2);
			if(v2==lca) swap(v1, v2);
			if(v1==lca) {
				update(root[v2], v3, 1);
				if(v1!=1) update(fa[root[v1]], v3, -1);
			}
			else {
				update(root[v1], v3, 1), update(root[v2], v3, 1);
				update(lca, v3, -1);
				if(lca!=1) update(fa[lca], v3, -1);
			}
		}
	}
	unset(root[1]);
	for(int i=1; i<=n; ++i) cout << ans[i] << endl;
	return 0;
}
2023/5/27 17:22
加载中...