「2026 杭电多校 5」1011. 树形广播

发表于 2026-08-05 分类于杭电多校本文字数： 1.1k 阅读时长 ≈ 1 分钟

Description

Link：https://acm.hdu.edu.cn/contest/problem?cid=1233&pid=1011

给出一棵包含 $n$ 个节点的树。每个节点都有一个显示值（初始均为 $0$ ）。定义 $dist(u, v)$ 表示节点 $u, v$ 之间的边数。

有 $Q$ 次操作，每次操作形如以下的两种：

1 v l r k $w_0 \ w_1 \ \dots \ w_k$ ：表示从节点 $v$ 发起广播，对于所有满足 $l \leq dist(u, v) \leq r$ 的节点 $u$ ，记 $d = dist(u, v)$ ，将节点 $u$ 的显示值修改为

\left(\sum_{i = 0}^k w_id^i\right) \bmod 998244353

2 x：查询节点 $x$ 当前的显示值。

数据范围： $1 \leq n, Q \leq 10^5$ ， $0 \leq k \leq 10$ ， $0 \leq w_i < 998244353$ 。

时空限制： $10$ s / $512$ MiB。

Solution

注意此题的修改操作为树上空心圆邻域赋值，而非树上空心圆邻域加（而且题目的算式是一个和树上距离有关的多项式）。这其实好做很多，我们只需要求出每个点被修改的最大时间戳，然后直接根据定义进行多项式求值即可。

使用点分树，记录每个节点到其所有祖先的距离以及所属分支（详见代码实现中的 bel 数组）。

每次更新时，不断地在点分树上从修改点向上跳。对于修改节点 $v$ 以及分治重心 $c$ ，当前连通块内与点 $c$ 之间的距离在区间 $[l - dist(v, c), r - dist(v, c)]$ 内的所有点都需要被更新（除了 $v$ 所属分支内的点），使用线段树进行标记永久化即可。

每次查询一个点的时候，也是不断地在点分树上从查询点向上跳。对于查询节点 $x$ 以及分治重心 $c$ ，在线段树上查询位置 $dist(x, c)$ 上的时间戳最大值，但每次查询时需要禁用 $x$ 所属分支。所以线段树上需要维护最大分支时间戳及其分支编号，以及次大分支时间戳。

时间复杂度 $\mathcal{O}(Q \log^2 n)$ 。

#include <bits/stdc++.h>

using i64 = long long;

#define debug(a) std::cout << #a << '=' << (a) << ' '

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int mod = 998244353;

const int N = 100100, MaxQ = 100100;

int n, Q;
std::vector<std::vector<int>> G;

int dep[N];
int anc[17][N];

void dfs_init(int u, int fu) {
    dep[u] = dep[fu] + 1;
    anc[0][u] = fu;
    for (int i = 1; i <= 16; i ++) {
        anc[i][u] = anc[i - 1][anc[i - 1][u]];
    }

    for (int v : G[u]) {
        if (v == fu) {
            continue;
        }
        dfs_init(v, u);
    }
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) std::swap(x, y);
    for (int i = 16; i >= 0; i --)
        if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
    if (x == y) return x;
    for (int i = 16; i >= 0; i --)
        if (anc[i][x] ^ anc[i][y]) x = anc[i][x], y = anc[i][y];
    return anc[0][x];
}

int pos[MaxQ];
std::vector<int> poly[MaxQ];

int func(std::vector<int> f, int x) {
    int y = 0;
    for (int w : f) {
        y = (1ll * y * x + w) % mod;
    }
    return y;
}

int ban[N];

int sz[N], mp[N];
int tot_sz, tot_rt;

void getRoot(int u, int fu) {
    sz[u] = 1, mp[u] = 0;
    for (int v : G[u]) {
        if (v == fu || ban[v]) {
            continue;
        }
        getRoot(v, u);
        sz[u] += sz[v];
        chmax(mp[u], sz[v]);
    }
    chmax(mp[u], tot_sz - sz[u]);
    if (!tot_rt || mp[u] < mp[tot_rt]) {
        tot_rt = u;
    }
}

int rt;
int Fa[N];
std::vector<std::pair<int, int>> bel[N];

void dfs(int u, int fu, int branch, int dist) {
    bel[u].push_back({branch, dist});
    for (int v : G[u]) {
        if (v == fu || ban[v]) {
            continue;
        }
        dfs(v, u, branch, dist + 1);
    }
}

void solve(int u) {
    ban[u] = 1;

    bel[u].push_back({u, 0});
    for (int v : G[u]) {
        if (ban[v]) {
            continue;
        }
        dfs(v, u, v, 1);
    }

    for (int v : G[u]) {
        if (ban[v]) {
            continue;
        }
        tot_sz = sz[v], tot_rt = 0;
        getRoot(v, u), Fa[tot_rt] = u, solve(tot_rt);
    }
}

struct Info {
    int v1, c1;
    int v2;
    Info() {
        v1 = v2 = 0;
        c1 = -1;
    }
    void insert(int v, int c) {
        if (v > v1) {
            if (c == c1) {
                v1 = v;
            } else {
                v2 = v1;
                v1 = v, c1 = c;
            }
        } else if (v > v2) {
            if (c != c1) {
                v2 = v;
            }
        }
    }
    int get(int c) {
        return c1 != c ? v1 : v2;
    }
};

int root[N];
namespace SGT {
    const int pond = 20001000;

    int nodeCount;
    struct node {
        int lc, rc;
        Info info;
    } t[pond];

    int create() {
        int p = ++ nodeCount;
        t[p].lc = t[p].rc = 0, t[p].info = Info();
        return p;
    }

    void init() {
        nodeCount = 0;
        for (int i = 1; i <= n; i ++) {
            root[i] = 0;
        }
    }

    void change(int &p, int l, int r, int s, int e, int v, int c) {
        if (!p) p = create();
        if (s <= l && r <= e) {
            t[p].info.insert(v, c);
            return;
        }
        int mid = (l + r) >> 1;
        if (s <= mid) {
            change(t[p].lc, l, mid, s, e, v, c);
        }
        if (mid < e) {
            change(t[p].rc, mid + 1, r, s, e, v, c);
        }
    }

    int ask(int p, int l, int r, int x, int c) {
        if (l == r) {
            return t[p].info.get(c);
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            return std::max(ask(t[p].lc, l, mid, x, c), t[p].info.get(c));
        } else {
            return std::max(ask(t[p].rc, mid + 1, r, x, c), t[p].info.get(c));
        }
    }
}

void add(int u, int l, int r, int t) {
    SGT::change(root[u], 0, n, l, r, t, -1);
    for (int i = (int)bel[u].size() - 2, x = Fa[u]; i >= 0; i --, x = Fa[x]) {
        auto [branch, dist] = bel[u][i];
        if (r - dist >= 0) {
            SGT::change(root[x], 0, n, std::max(0, l - dist), r - dist, t, branch);
        }
    }
}

int ask(int u) {
    int t = 0;
    chmax(t, SGT::ask(root[u], 0, n, 0, 0));
    for (int i = (int)bel[u].size() - 2, x = Fa[u]; i >= 0; i --, x = Fa[x]) {
        auto [branch, dist] = bel[u][i];
        chmax(t, SGT::ask(root[x], 0, n, dist, branch));
    }
    return t;
}

void work() {
    std::cin >> n >> Q;

    G.assign(n + 1, {});
    for (int i = 1; i < n; i ++) {
        int x, y;
        std::cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs_init(1, 0);

    poly[0] = {0};
    for (int i = 1; i <= n; i ++) {
        bel[i].clear();
    }

    for (int i = 1; i <= n; i ++) {
        ban[i] = 0;
        Fa[i] = 0;
        bel[i].clear();
    }
    tot_sz = n, tot_rt = 0;
    getRoot(1, 0), rt = tot_rt, solve(tot_rt);

    SGT::init();

    for (int i = 1; i <= Q; i ++) {
        int opt, u, l, r, k;
        std::cin >> opt >> u;
        if (opt == 1) {
            std::cin >> l >> r >> k;
            std::vector<int> s(k + 1);
            for (int i = k; i >= 0; i --) {
                std::cin >> s[i];
            }
            poly[i] = s, pos[i] = u;
            add(u, l, r, i);
        } else {
            int t = ask(u), ans;
            if (t == 0) {
                ans = 0;
            } else {
                int v = pos[t];
                int d = dep[u] + dep[v] - 2 * dep[lca(u, v)];
                // debug(t), debug(v), debug(d) << '\n';
                ans = func(poly[t], d);
            }
            std::cout << ans << '\n';
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    std::cin >> T;

    while (T --) {
        work();
    }

    return 0;
}

/*
1
5 1
1 2
2 3
2 4
4 5
2 3

1
5 3
1 2
2 3
2 4
4 5
2 3
1 2 1 2 0 7
2 2

1
5 9
1 2
2 3
2 4
4 5
2 3
1 2 1 2 0 7
2 2
2 5
1 5 1 3 1 2 3
2 4
2 3
2 1
2 5
*/