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

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

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

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

    有 QQ 次操作,每次操作形如以下的两种:

    • 1 v l r k w0 w1 … wkw_0 \ w_1 \ \dots \ w_k:表示从节点 vv 发起广播,对于所有满足 l≤dist(u,v)≤rl \leq dist(u, v) \leq r 的节点 uu,记 d=dist(u,v)d = dist(u, v),将节点 uu 的显示值修改为
    (∑i=0kwidi) mod 998244353\left(\sum_{i = 0}^k w_id^i\right) \bmod 998244353
    • 2 x:查询节点 xx 当前的显示值。

    数据范围:1≤n,Q≤1051 \leq n, Q \leq 10^5,0≤k≤100 \leq k \leq 10,0≤wi<9982443530 \leq w_i < 998244353。

    时空限制:1010s / 512512MiB。

    Solution

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

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

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

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

    时间复杂度 O(Qlog⁡2n)\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
    */