求条
查看原帖
求条
1388054
qjy1024楼主2024/12/12 18:19
#include <bits/stdc++.h>
#define int __int128_t
#define range(VAR, START, END, STEP) for (int(VAR) = (START); (STEP) * (VAR) <= (STEP) * (END); (VAR) += (STEP))
#define loop(END) for (int i = 1; i <= (END); i++)
#define MAXN (signed)(1e5 + 10)
#define pr() putchar('\n')
#define ps() putchar(' ')
#define init(arr, val) memset(arr, val, sizeof(arr))
#define abs_v(x) ((x) >= 0 ? (x) : (-(x)))
using namespace std;
int rt()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    return 1e9 + 10;
}
const int inf = rt();
int read()
{
    int nm = 0, zf = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            zf = -1;
    for (; isdigit(c); c = getchar())
        nm = nm * 10 + (c - '0');
    return nm * zf;
}
void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}
vector<int> G[MAXN];
// vector<pair<int, int>> V[MAXN];
int fa[MAXN][25], dep[MAXN];
void dfs_lca(int f, int u)
{
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for (auto x : G[u])
    {
        if (x == f)
            continue;
        dfs_lca(u, x);
    }
}
int lowbit(int x)
{
    return x & -x;
}
int LCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = dep[x] - dep[y]; i; i -= lowbit(i))
    {
        int step = log2((long long)lowbit(i));
        x = fa[x][step];
    }
    if (x == y)
        return x;
    range(i, 20, 1, -1)
    {
        if (fa[x][i] == fa[y][i])
            continue;
        x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}
struct node
{
    int typ, val, l, r;
} w[MAXN * 70];
int root[MAXN], ans[MAXN];
int top = 0;
#define mid ((l) + (r) >> 1)
void update(int x)
{
    if (w[w[x].l].val <= w[w[x].r].val)
    {
        w[x].val = w[w[x].l].val;
        w[x].typ = w[w[x].l].typ;
    }
    else
    {
        w[x].val = w[w[x].r].val;
        w[x].typ = w[w[x].r].typ;
    }
}
int merge(int x, int y, int l, int r)
{
    if (x == 0 || y == 0)
        return x + y;
    if (l == r)
    {
        w[x].val += w[y].val;
        return x;
    }
    w[x].l = merge(w[x].l, w[y].l, l, mid);
    w[x].r = merge(w[x].r, w[y].r, mid + 1, r);
    update(x);
    return x;
}
int change(int u, int l, int r, int p, int k)
{
    if (u == 0)
        u = ++top;
    if (l == r)
    {
        w[u].val += k;
        w[u].typ = p;
        return u;
    }
    if (p <= mid)
        w[u].l = change(w[u].l, l, mid, p, k);
    else
        w[u].r = change(w[u].r, mid + 1, r, p, k);
    update(u);
    return u;
}
void calc(int u, int f)
{
    for (auto x : G[u])
    {
        if (x == f)
            continue;
        calc(x, u);
        root[u] = merge(root[u], root[x], 1, MAXN);
    }
    ans[u] = (w[root[u]].val ? w[root[u]].typ : 0);
}
signed main()
{
    int n = read(), m = read();
    range(i, 1, n - 1, 1)
    {
        int x = read(), y = read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs_lca(1, 1);
    range(j, 1, 20, 1)
    {
        range(i, 1, n, 1)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    range(i, 1, m, 1)
    {
        int x = read(), y = read(), v = read();
        int lca = LCA(x, y);
        root[x] = change(root[x], 1, MAXN, v, 1);
        root[y] = change(root[y], 1, MAXN, v, 1);
        root[lca] = change(root[lca], 1, MAXN, v, -1);
        root[fa[lca][0]] = change(root[fa[lca][0]], 1, MAXN, v, -1);
    }

    calc(1, 0);
    range(i, 1, n, 1)
    {
        write(ans[i]);
        putchar('\n');
    }
    return EXIT_SUCCESS;
}
2024/12/12 18:19
加载中...