#15-18RE+#19-20TLE,求条qwq
查看原帖
#15-18RE+#19-20TLE,求条qwq
927155
_Elysia_楼主2024/3/14 13:58
#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = l + r >> 1
using namespace std;
const int N = 1e5 + 20;
ll n, m, s = 1, ans[N<<1];

ll cnt = 1, h[N<<2];
struct node{
	ll v, nxt;
}e[N<<2];
void add_edge(ll u, ll v) {
	e[++cnt] = (node){v, h[u]};
	h[u] = cnt;
}


ll fa[N][25], dep[N<<1];
void dfs1(ll u, ll f) {
	dep[u] = dep[f] + 1;
	fa[u][0] = f;
	for(int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; 
	for(int i = h[u]; i; i = e[i].nxt) {
		ll v = e[i].v;
		if(v == f) continue;
		dfs1(v, u);
	}
}
ll lca(ll u, ll v) {
	if(dep[v] > dep[u]) swap(u, v);
	for(int i = 20; i >= 0; i--) {
		if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	}
	if(u == v) return u;
	for(int i = 20; i >= 0; i--) {
		if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}

ll tot = 0, sum[N<<5], ls[N<<5], rs[N<<5], t[N<<5], root[N<<5];

//inline ll ls(ll x) {return x << 1};
//inline ll rs(ll x) {return x << 1 | 1};

void up(ll p) {
	if(sum[ls[p]] >= sum[rs[p]]) {
		t[p] = t[ls[p]];
		sum[p] = sum[ls[p]];
	}
	else {
		t[p] = t[rs[p]];
		sum[p] = sum[rs[p]];
	}
}

void change(ll &p, ll l, ll r, ll x, ll k) {
	if(!p) p = ++tot;
	if(l == r) {sum[p] += k; t[p] = x; return;}
	Mid;
	if(x <= mid) change(ls[p], l, mid, x, k);
	else         change(rs[p], mid+1, r, x, k);
	up(p);
}

ll merge(ll p, ll pre, ll l ,ll r) {
	if(!p || !pre) return p + pre;
	if(l == r) {sum[p] += sum[pre]; return p;}
	Mid;
	ls[p] = merge(ls[p], ls[pre], l, mid);
	rs[p] = merge(rs[p], rs[pre], mid+1, r);
	up(p);
	return p;
}

void dfs2(ll u, ll f) {
	for(int i = h[u]; i; i = e[i].nxt) {
		ll v = e[i].v;
		if(v == f) continue;
		dfs2(v, u);
		root[u] = merge(root[u], root[v], 1, N - 20);
	}
	ans[u] = sum[root[u]] ? t[root[u]] : 0;
}
int main (){
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n; i++) {
		ll u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs1(s, 0);
	for(int i = 1; i <= m; i++) {
		ll u, v, z;
		scanf("%d%d%d", &u, &v, &z);
		ll p = lca(u, v);
		change(root[u], 1, N - 20, z, 1);
		change(root[v], 1, N - 20, z, 1);
		
		change(root[p], 1, N - 20, z, -1);
		change(root[fa[p][0]], 1, N - 20, z, -1);
		
	}
	dfs2(s, 0);
	for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	
	return 0;
} 
2024/3/14 13:58
加载中...