RE #19 #20 求助

#include <iostream>
#include <cstdio>
#include <vector>
#define NN 2000000
#define N 100000
using namespace std;
int n,m;
int nodes,rt[NN],rtsz,ch[NN][2],seg[NN],gg[NN],ans[N];
vector<int> G[N];
vector<int> increase[N],decrease[N];
int f[N][20],deep[N];
/////////////////////////////////////////////////////////
void dfs_lca(int u,int fa) {
	deep[u]=deep[fa]+1;
	for (auto v:G[u]) {
		if (v==fa) continue;
		dfs_lca(v,u);
		f[v][0]=u;
	}
}
int LCA(int u,int v) {
	int du=deep[u],dv=deep[v];
	if (du<dv) {
		swap(u,v);
		swap(du,dv);
	}
	for (int j=19;j>=0;j--) {
		if (du-(1<<j)>=dv) {
			u=f[u][j];
			du-=(1<<j);
		}
	}
    if (u==v) return u;
	for (int j=19;j>=0;j--) {
		if (f[u][j]!=f[v][j]) {
			u=f[u][j];
			v=f[v][j];
		}
	}
	return f[u][0];
}
/////////////////////////////////////////////////////////
void up(int u) {
	if (gg[ch[u][0]]>gg[ch[u][1]]) {
		gg[u]=gg[ch[u][0]];
		seg[u]=seg[ch[u][0]];
	} else if (gg[ch[u][0]]<gg[ch[u][1]]) {
		gg[u]=gg[ch[u][1]];
		seg[u]=seg[ch[u][1]];
	} else {
		if (seg[ch[u][0]]<seg[ch[u][1]]) {
			gg[u]=gg[ch[u][0]];
			seg[u]=seg[ch[u][0]];
		} else if (seg[ch[u][0]]>seg[ch[u][1]]) {
			gg[u]=gg[ch[u][1]];
			seg[u]=seg[ch[u][1]];
		} else {
			seg[u]=seg[ch[u][1]];
			gg[u]=gg[ch[u][0]]+gg[ch[u][1]];
		}
	}
}
void update(int &u,int l,int r,int d,int f) {
	if (!u) u=++nodes;
	if (l==r) {
		gg[u]+=f;
		seg[u]=l;
		return;
	}
	int mid=l+r>>1;
	if (d<=mid) update(ch[u][0],l,mid,d,f);
	else update(ch[u][1],mid+1,r,d,f);
	up(u);
}
struct __QWQ__{
	int maxx,maxid;
	void get_new(__QWQ__ __) {
		if (maxx>__.maxx) {
		} else if (maxx<__.maxx) {
			maxx=__.maxx;
			maxid=__.maxid;
		} else {
			if (maxid<__.maxid) {
			} else if (maxid>__.maxid) {
				maxid=__.maxid;
				maxx=__.maxx;
			} else {
				maxid=__.maxid;
				maxx+=__.maxx;
			}
		}
	}
};
__QWQ__ query(int u,int l,int r,int ll,int rr) {
	if (u==0) return __QWQ__{-1,-1};
	if (ll<=l&&r<=rr) return __QWQ__{gg[u],seg[u]};
	int mid=l+r>>1;
	__QWQ__ ans={-1,-1};
	if (ll<=mid) ans.get_new(query(ch[u][0],l,mid,ll,rr));
	if (rr>mid) ans.get_new(query(ch[u][1],mid+1,r,ll,rr));
	return ans;
}
void merge(int &a,int b,int l,int r) {
	if (!a) {a=b;return;}
	if (!b) return;
	if (l==r) {
		seg[a]=l;
		gg[a]+=gg[b];
		return;
	}
	int mid=l+r>>1;
	merge(ch[a][0],ch[b][0],l,mid);
	merge(ch[a][1],ch[b][1],mid+1,r);
	up(a);
}
int dfs(int u,int fa,int &siz) {
	int nowroot=-1,nowsize=0;
	siz=0;
	for (auto v:G[u]) {
		if (v==fa) continue;
		if (nowroot==-1) {
			nowroot=dfs(v,u,nowsize);
		} else {
			int vs1;
			int vs2=dfs(v,u,vs1);
			siz+=vs1;
			if (nowsize>vs1) {
				merge(nowroot,vs2,1,1e5);
			} else {
				merge(vs2,nowroot,1,1e5);
				nowroot=vs2;
			}
			nowsize+=vs1;
		}
	}
	if (nowroot==-1) {
		rt[++rtsz]=++nodes;
		nowroot=nodes;
	}
	for (auto it:increase[u])
		update(nowroot,1,1e5,it,1);
	for (auto it:decrease[u])
		update(nowroot,1,1e5,it,-1);
	ans[u]=query(nowroot,1,1e5,1,1e5).maxid;
	return nowroot;
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i=1,u,v;i<n;i++) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs_lca(1,0);
	for (int j=1;j<=19;j++)
		for (int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	for (int u,v,w,i=1;i<=m;i++) {
		cin >> u >> v >> w;
		increase[u].push_back(w);
		increase[v].push_back(w);
		int lca=LCA(u,v);
		decrease[lca].push_back(w);
		decrease[f[lca][0]].push_back(w);
	}
	int vv;
	dfs(1,0,vv);
	for (int i=1;i<=n;i++) cout << ans[i] << endl;
	return 0;
}