原题链接
每个点开一个权值线段树，然后用树上差分的方法修改，最后自底向上暴力线段树合并即可。
不过空间较大，会(MLE)，写个内存池就可以了。
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
const int M = 6e6 + 10;
struct dd {
int x, y, z;
};
dd a[N];
int fi[N], di[N << 1], ne[N << 1], ro[N], S[M], CO[M], L[M], R[M], de[N], f[N][18], an[N], sta[M], l, ma, gn, SEG, tp;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline void add(int x, int y)
{
di[++l] = y;
ne[l] = fi[x];
fi[x] = l;
}
inline void sw(int &x, int &y)
{
int z = x;
x = y;
y = z;
}
inline int maxn(int x, int y){ return x > y ? x : y; }
void dfs(int x)
{
int i, y;
for (i = 1; i <= gn; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (i = fi[x]; i; i = ne[i])
if (!de[y = di[i]])
{
de[y] = de[x] + 1;
f[y][0] = x;
dfs(y);
}
}
int lca(int x, int y)
{
int i;
if (de[x] > de[y])
sw(x, y);
for (i = gn; ~i; i--)
if (de[f[y][i]] >= de[x])
y = f[y][i];
if (!(x ^ y))
return x;
for (i = gn; ~i; i--)
if (f[x][i] ^ f[y][i])
{
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
void pp(int r)
{
int lx = L[r], rx = R[r];
if (S[lx] < S[rx])
{
S[r] = S[rx];
CO[r] = CO[rx];
}
else
{
S[r] = S[lx];
CO[r] = CO[lx];
}
}
inline void rec(int x){ sta[++tp] = x; }
inline int NEW(){ return tp ? sta[tp--] : ++SEG; }
void mdf(int &r, int x, int y, int k, int v)
{
if (!r)
r = ++SEG;
if (!(x ^ y))
{
S[r] += v;
S[r] > 0 ? CO[r] = x : CO[r] = 0;
return;
}
int mid = (x + y) >> 1;
k <= mid ? mdf(L[r], x, mid, k, v) : mdf(R[r], mid + 1, y, k, v);
pp(r);
}
int merge(int x, int y, int r_1, int r_2)
{
if (!r_1)
return r_2;
if (!r_2)
return r_1;
int r = NEW();
if (!(x ^ y))
{
S[r] = S[r_1] + S[r_2];
S[r] > 0 ? CO[r] = x : CO[r] = 0;
return r;
}
int mid = (x + y) >> 1;
L[r] = merge(x, mid, L[r_1], L[r_2]);
R[r] = merge(mid + 1, y, R[r_1], R[r_2]);
pp(r);
rec(r_1);
rec(r_2);
return r;
}
void UPD(int x)
{
int i, y;
for (i = fi[x]; i; i = ne[i])
if ((y = di[i]) ^ f[x][0])
{
UPD(y);
ro[x] = merge(1, ma, ro[x], ro[y]);
}
an[x] = CO[ro[x]];
}
int main()
{
int i, n, m, x, y, LCA;
n = re();
m = re();
gn = log2(n);
for (i = 1; i < n; i++)
{
x = re();
y = re();
add(x, y);
add(y, x);
}
de[1] = 1;
dfs(1);
for (i = 1; i <= m; i++)
{
a[i].x = re();
a[i].y = re();
a[i].z = re();
ma = maxn(ma, a[i].z);
}
for (i = 1; i <= m; i++)
{
LCA = lca(a[i].x, a[i].y);
mdf(ro[a[i].x], 1, ma, a[i].z, 1);
mdf(ro[a[i].y], 1, ma, a[i].z, 1);
mdf(ro[LCA], 1, ma, a[i].z, -1);
if (LCA ^ 1)
mdf(ro[f[LCA][0]], 1, ma, a[i].z, -1);
}
UPD(1);
for (i = 1; i <= n; i++)
printf("%d
", an[i]);
return 0;
}