「2026 杭电多校 5」1011. 树形广播
https://acm.hdu.edu.cn/contest/problem?cid=1233&pid=1011
给出一棵包含 n 个节点的树。每个节点都有一个显示值(初始均为 0)。定义 dist(u, v) 表示节点 u, v 之间的边数。
有 Q 次操作,每次操作形如以下的两种:
1 v l r kw_0 \ w_1 \ \dots \ w_k:表示从节点 v 发起广播,对于所有满足 l \leq dist(u, v) \leq r 的节点 u,记 d = dist(u, v),将节点 u 的显示值修改为
2 x:查询节点 x 当前的显示值。
数据范围:1 \leq n, Q \leq 10^5,0 \leq k \leq 10,0 \leq w_i < 998244353。
时空限制:10s / 512MiB。
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
*/