XCPC wiki - 树习题集

树上思维

2024 CCPC 济南 L. Intersection of Paths

在树上选择$k$ 条路径，路径的$2k$ 个端点必须互不相同。最大化被所有路径包含的边权之和。有多次询问，每次询问会临时修改一条边的边权。每次询问的 k 可能不同。

节点数、询问数$5 \times 10^{5}$。

可能被端点两两不同的$k$ 条路径包含的边，需要满足把这条边去掉之后，形成的两个连通块大小都大于等于$k$。在$k$ 固定的情况下，这些边形成了一棵树。所以答案就是这棵树的直径。

$k$ 变化的时候怎么办？注意到$k + 1$ 的树被$k$ 的树完全包含，所以可以将所有询问按 k 从小到大排序，依次处理。

问题变为：每次询问临时修改一条边的边权，以及在$k$ 变大时永久删掉若干条边，求树直径。删掉边可以转化为将边权改成$0$。

这就是经典的动态树直径问题。

复杂度$\Theta(n \log n + q(\log n + \log q))$。

int n = read(), q = read();

for (int id = 1; id < n; id++) {
    int u = read(), v = read();
    w[id] = read();
    E[u].emplace_back(v, id);
    E[v].emplace_back(u, id);
}

init();

vector<vector<int>> vec(n);
for (int id = 1; id < n; id++) {
    int v = son[id];
    vec[min(siz[v], n - siz[v])].push_back(id);
}

vector<vector<tuple<int, int, int>>> que(n);
for (int qid = 0; qid < q; qid++) {
    int id = read(), e = read(), k = read();
    que[k].emplace_back(id, e, qid);
}

vector<ll> ans(q);
for (int k = 1; k < n; k++) {
    for (auto& [id, e, qid] : que[k]) {
        int old = w[id];
        if (old) change(id, e);
        ans[qid] = get();
        change(id, old);
    }
    for (auto& id : vec[k]) {
        change(id, 0);
    }
}

for (int i = 0; i < q; i++) {
    printf("%lld\n", ans[i]);
}

2024 杭电多校 8008 - cats 的数据结构

给定以$1$ 为根的树，树上的每个节点$i$ 都有两个整数权值$a_i,b_i$。现在你需要为每个节点确定权值$a_i,b_i$，使得这个树满足以下四个条件：

1. 对于任意的$i$，都有$1\leq a_i,b_i\leq 10^9$。
2. 对于任意的一对$u,v$，都有$a_u\neq a_v$ 且$b_u\neq b_v$。
3. 对于任意的一对$u,v$，若$u$ 是$v$ 的祖先，则$a_u>a_v$ 且$b_u>b_v$。
4. 对于任意的一对$u,v$，若$a_u>a_v$ 且$b_u>b_v$，则$u$ 是$v$ 的祖先。

给出所有合法构造方式中使序列$a_1,b_1,a_2,b_2,\dots a_n,b_n$ 字典序最小的解。([[…/contests/2024杭电多校/2024-08-12：2024“钉耙编程”中国大学生算法设计超级联赛（8）|2024-08-12：2024“钉耙编程”中国大学生算法设计超级联赛（8）]])

int n;
cin >> n;
vector<vector<int>> E(n);
for (int u = 1; u < n; ++u) {
    int p = read();
    p--;
    E[p].push_back(u);
}

vector<int> mn(n), siz(n);
auto dfs1 = [&](this auto&& self, int u) -> void {
    mn[u] = u;
    siz[u] = 1;
    for (auto& v : E[u]) {
        self(v);
        mn[u] = min(mn[u], mn[v]);
        siz[u] += siz[v];
    }
};
dfs1(0);

for (int u = 0; u < n; ++u) {
    sort(E[u].begin(), E[u].end(), [&](const int& x, const int& y) {
        return mn[x] < mn[y];   // 保证字典序最小
    });
}

int now = 0;
vector<pair<int, int>> res(n);
auto dfs2 = [&](this auto&& self, int u, int d) -> void {
    int t = siz[u] - 1;
    for (auto& v : E[u]) {
        t -= siz[v];
        self(v, t + d);
    }
    res[u] = { ++now, siz[u] + d };
};
dfs2(0, 0);

for (auto& [a, b] : res) {
    cout << a << " " << b << " ";
}
cout << "\n";

2024 杭电多校 3001 - 深度自同构

[[…/contests/2024杭电多校/2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）#3004 - 深度自同构|2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）]]

题意 求有$n$ 个节点的无编号有根森林的数量，满足：

• 森林中任意两个深度相同的节点都有相同的度。

思路 设$f_{i} = \sum_{d\mid i-1}f_{d}$ 为$i$ 个点的合法树个数，则$\operatorname{ans}_{i}=\sum_{d\mid i}f_{i}$，事实上，$f_{i}=\operatorname{ans}_{i-1}$，使用 [[…/数学/质数与约数#枚举 1 ~ N 每个数的约数|枚举约数]] 实现$\Theta(n\log n)$ 的复杂度。

int n = read();
ans[0] = 1;
for (int i = 1; i <= n; i++) {
    f[i] = ans[i - 1];
    for (int j = i; j <= n; j += i) {
        ans[j] += f[i];
        ans[j] %= MOD;
    }
    printf("%lld ", ans[i]);
}

造花

int n;
cin >> n;
vector<vector<int>> E(n);
vector<int> deg(n);

for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    E[u].push_back(v);
    E[v].push_back(u);
    deg[u]++, deg[v]++;
}

for (int u = 0; u < n; ++u) {
    if (deg[u] != 2) continue;
    int sum = 0;
    for (auto v : E[u]) {  // 不能加引用&
        if (deg[v] == 2) {
            if (E[v][0] == u) v = E[v][1];
            else v = E[v][0];
            sum++;
        }
        sum += deg[v];
    }
    if (sum == n - 1) {
        cout << "Yes\n";
        return;
    }
}
cout << "No\n";

2024 牛客多校 4F - Good Tree

[[…/contests/2024牛客多校/2024-07-25：2024牛客暑期多校训练营4#F - Good Tree(138 + 40)|2024-07-25：2024牛客暑期多校训练营4]]

题意 对树上节点$u$，定义$f(u)=\sum d(u,v)$。给定$x$，求满足如下条件的$n$ 的最小值：

• $\exists u,v,\quad\text{s.t.}\quad f(u)-f(v)=x$。

思路 链状最优，二分答案，特判偶数。

ull n = read();
ull l = 1, r = 2e9 + 1, m;
auto check = [&](ull x) {
    if (x & 1) {
        x >>= 1;
        return x * x >= n;
    }
    else {
        x >>= 1;
        return x * x - x >= n;
    }
};
while (l <= r) check(m = l + r >> 1) ? r = m - 1 : l = m + 1;
if ((!(l & 1)) && (n & 1)) {
    l++;
}
printf("%llu\n", l);

2024 杭电多校 2008 - 成长，生命，幸福

[[…/contests/2024杭电多校/2024-07-22：2024“钉耙编程”中国大学生算法设计超级联赛（2）|2024-07-22：2024“钉耙编程”中国大学生算法设计超级联赛（2）]]

题意 Alice 作为德鲁伊，一棵神奇的树，这棵树会不断的成长。对于一个节点$i$ 的成长，先将这个节点变为$d_i$ 边型（$d_i$ 为这个点的度数），然后将原本与这个点相连的边随机匹配多边形上的点（一对一，不可重复），再随机删除由这个点变化成的多边形上的一条边。特别的，对于一个度数为$0$ 或$1$ 的点，进行成长将不会发生变化。对于一棵树的成长，定义为树上所有的节点进行一次成长。Alice 认为一棵树的直径越长，长得越好，所以 Alice 想要知道，在这棵树进行$m$ 次成长后，直径的长度最大可能是多少。这里定义树的直径的长度为直径上的点数。答案对$10^9+7$ 取模。数据范围：$1 \leqslant n \leqslant 10^{5},\ 1 \leqslant m \leqslant 10^{9}$。

思路

• 取点权为$w_{i}=d_{i}+(d_{i}-1)\cdot (2^{m}-2)$，边权为 1，跑树直径。
• 点权可能很大。注意到$\sum d_{i} = 2 m < 2 \times 10^{5}$，故当$2^{m}-2>2\times 10^{5}$ 时，$d_{i}$ 的贡献不可能超过$(d_{i}-1)\cdot (2^{m}-2)$ 的贡献，因此这时可以将$2^{m}-2$ 视为$2\times 10^{5}$。

constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;

vector<int> E[N];
ll w[N], dep[N];
int c, deg[N], lst[N];
void dfs(int u, int p = 0) {  // 树直径板子
    lst[u] = p;
    for (auto& v : E[u]) {
        if (v != p) {
            dep[v] = dep[u] + w[v];
            if (dep[v] > dep[c]) c = v;
            dfs(v, u);
        }
    }
}

void eachT() {
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        E[i].clear();
        deg[i] = 0;
        lst[i] = 0;
    }  // init
    c = 0;

    if (n == 1) {
        printf("1\n");
        return;
    }

    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
        deg[u]++, deg[v]++;  // 度数
    }

    ll poww;
    if (m > 50) poww = 0x3f3f3f3f;
    else poww = (1ll << m) - 2;
    for (int i = 1; i <= n; i++) {
        w[i] = deg[i] + (deg[i] - 1ll) * poww;
    }

    dep[1] = 0, dfs(1);
    dep[c] = 0, dfs(c);  // 两次DFS求树直径

    ll ans = 0;
    poww = (qpow(2, m) - 2 + MOD) % MOD;
    for (int i = c; i; i = lst[i]) {   // 遍历直径 计算答案
        ans += deg[i] + (deg[i] - 1ll) * poww;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}

洛谷 P3304 - 直径

求所有直径都经过的边的数量。

int i = nxt[0], res = 0;
while (dep[c] - dep[i] != dis[i]) {
    i = nxt[i];
}
while (dep[i] != dis[i]) {
    i = lst[i];
    res++;
}
printf("%lld\n", res);

VJwin8G - 古老的神树

题意 有一棵$n$ 个点的无向无权且根为$1$ 的树，你可以用一次特殊技能“跳跃”，从$1$ 点到达任意点或回到$1$ 点，不耗时间。$\forall 1 \leqslant i \leqslant n$，你需要设计一条以$1$ 为起终点的环路，使得你经过不重复的$i$ 个点，且时间最少。

思路 当没有特殊技能时，我们每向下到达一个点和向上离开一个点需要经过两次这个点上面的边，所以答案为$2 \times (i-1)$，如$k=4: 1-2-4-2-1-3-1$。

当拥有特殊技能时，可以让向下到达或向上离开一个点的过程加速（因为是环路，这本质上是等价的），希望跳跃更多的距离，那最大的距离当然是深度，具体的操作就是让经过的点的最大深度最大。而有$i$ 个点要被经过的时候理论最大深度为$i-1$。

因此，用 DFS 求出整棵树最大深度为$d$，对于要经过$i$ 个点的情况，答案为$2 \times (i-1) - \min\{i-1,d\}$。

2023 ICPC 网络赛 (I) G. Spanning Tree

题意 最初，图中没有边，然后进行以下$n-1$ 操作：

• 从$a_i$ 所在的连接块中均匀概率地选择一个节点$u_i$ ，然后从$b_i$ 所在的连接块中均匀概率地选择一个节点$v_i$ ，然后添加一条边连接$u_i$ 和$v_i$。

给定一棵由$n$ 个节点组成的生成树，随机过程形成的生成树正是这棵生成树的概率是多少？注意，如果永远不可能生成这棵生成树，输出$0$。(2023 ICPC 网络赛 (I) G. Spanning Tree)

思路 按顺序连边并维护连通性，需要在$\Theta(1)$ 时间里判断出两个连通块之间有边（当然如果有边就只有一条边）。

「不要是一团，树要有树的形态。」

当我们把树根拎出来之后就能发现，每次合并的两个连通块在树上应该是相邻的（即有一条边将他们相连），也就是说这两者之一的父亲应该另一个连通块中，否则无解。

DSU dsu(n);
ll res = 1;
for (auto& [u, v] : que) {
    u = dsu.find(u), v = dsu.find(v);
    if (dsu.find(p[v]) == u) {
        (res *= dsu.size(u)) %= mod;
        (res *= dsu.size(v)) %= mod;
        dsu.uno(u, v);
    }
    else if (dsu.find(p[u]) == v) {
        (res *= dsu.size(u)) %= mod;
        (res *= dsu.size(v)) %= mod;
        dsu.uno(v, u);
    }
    else {
        res = 0;
    }
}
if (res) res = qpow(res, mod - 2);
cout << res << "\n";

CF1336A. Linova and Kingdom

题意 有根树，选择$k$ 个节点权值为$0$，其余权值为$1$。一个权值为$0$ 的点对答案的贡献是它到根的路径上的权值和，最大化所有节点贡献之和。

思路 如果有个点被选，那么所有它的后代节点都要被选。因此每个点对答案的真实贡献是 dep-siz。因此对前$k$ 大的 dep[u] - siz[u] 之和。

树上思维——树上大力分讨

要不重不漏地考虑所有情况。

树上询问

题意 树。$n$ 个点。有$q$ 次询问，每次询问给出一个三元组$(a,b,c)$，求有多少个$i$ 满足这棵树在以$i$ 为根时$\operatorname{lca}(a,b)=c$。

int u = read(), v = read(), lca = read(), ans = 0;
if (getlca(getlca(getlca(u, v), lca), lca) == lca) {  // lca在最顶上
    if (getson(lca, u) != getson(lca, v)) ans = n - siz[getson(lca, u)] - siz[getson(lca, v)];  // 不在一个叶子上
    else ans = 0;  // 在一个叶子上
} else {
    if (getlca(u, lca) == lca) ans = siz[lca] - siz[getson(lca, u)];  // lca在u上面
    else if (getlca(v, lca) == lca) ans = siz[lca] - siz[getson(lca, v)];  // lca在v上面
    else ans = 0;
}
printf("%d\n", ans);

树上思维——树上博弈

CF2013F1. Game in Tree (Easy Version)

Alice 和 Bob 树上博弈，Alice 从顶点$1$ 开始，且为先手，而 Bob 从顶点$t$ 开始。在他们的回合中，玩家必须从当前顶点移动到尚未被任何人访问过的相邻顶点。第一个无法移动的玩家输掉游戏。判断胜负。

int s = 0, t;
cin >> t;
t--;

// 找到s-t路径上所有点
vector<int> vis(n), from(n, -1), path;
auto dfs = [&](this auto&& self, int u, int p) {
	if (u == t) {
		while (u != -1) {
			path.push_back(u);
			vis[u] = 1;
			u = from[u];
		}
		return;
	}

	for (auto v : E[u]) {
		if (v == p) continue;
		from[v] = u;
		self(v, u);
	}
};
dfs(s, -1);

const int m = path.size();

// 从s-t路径上每个点出发，找到最远的点
auto dfs2 = [&](this auto&& self, int u, int p) -> int {
	int d = 0;
	for (auto v : E[u]) {
		if (v == p || vis[v]) continue;
		d = max(d, self(v, u) + 1);
	}
	return d;
};
vector<int> dep(m);
for (int i = 0; i < m; i++) {
	dep[i] = dfs2(path[i], -1);
}

// 博弈
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
	a[i] = dep[m - 1 - i] + i;
	b[i] = dep[i] + i;
}

RMQ A(a), B(b);
for (int i = 0; i < (m + 1) / 2; i++) {
	if (a[i] > B(i, m - i - 1)) {
		cout << "Alice" << endl;
		return;
	}
	if (i < m / 2 && b[i] >= A(i + 1, m - i - 1)) {
		cout << "Bob" << endl;
		return;
	}
}
assert(false);

题意 狗星有$n$ 个地区，有$n - 1$ 条双向道路使狗星的所有地区连通。猫咪军团要投放一些猫咪到狗星的某些地区上以抓捕狗仔。猫咪们修建了$m$ 条猫咪通道。一条猫咪通道连接两个不同的点$u,v$，并且猫咪通道上有一个中转站，猫咪想从$u$ 走到$v$ 或从$v$ 走到$u$ 时，需要先走到中转站，再从中转站走到另一个点。当某只猫咪在某个中转站时，若狗星道路上也有一条边连接$u$ 和$v$，视为这只猫咪在狗星道路的这条路中间。猫咪只能走猫咪通道，狗仔只能走狗星道路。

游戏规则：猫咪军团先投放猫咪，狗仔再选择初始位置。猫咪和狗仔交替行动，由猫咪先手（事实上先后手不影响结果）。猫咪军团选择一只猫咪，然后让它从一个地区走到一个中转站上，或者从中转站走到一个地区上（只能走一次，经过半条猫咪通道）。狗仔军团选择狗仔通过狗星的道路移动到另一个地区（可以经过任意条道路和地区，只要路径中间及路径经过的地区没有猫咪），也可以原地不动。 多只猫咪可以待在同一个地区，猫咪们和狗仔都知道彼此的位置；猫咪通道不一定将狗星的所有地区连通。

任何时刻，只要有猫咪和狗仔在同一个地区，就视作抓捕成功。在保证能抓捕住狗仔的情况下，最小化要投放的猫咪的数量。(2024 杭电多校 5007 - 猫咪军团侵略狗星 [[…/contests/2024杭电多校/2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）|2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）]])

思路 如果猫图由多个连通块构成，那么每个连通块至少要有一只猫咪。分别考虑每个连通块，设某个连通块的点集为 U 。若狗图中有某条边连接了 U 中的两个点，且猫图中不含有这条边，那么这个连通块需要 2 只猫咪，否则需要 1 只猫咪。代码极其简单，此处省略。

树和博弈 CF-1404B

题意 树上博弈。两人从起始点$a,b$ 轮流跳，每次跳跃上界为$d_{a},d_{b}$。若 A 和 B 重合，则 A 胜，否则在足够长的时间内都不能重合，则 B 胜。判断胜负。（[[…/数学/博弈论#J. 树和博弈 CF-1404B]]）

bool ans;
if (getd(a, b) <= da) ans = 1;          // 一步就死
else if (da >= db) ans = 1;             // A 的跳远更牛
else if (d <= 2 * da) ans = 1;          // A 全覆盖
else if (db >= 2 * da + 1) ans = 0;     // B 来回跳跃
else ans = 1;
printf("%s\n", ans ? "Alice" : "Bob");

合法 DFS 序与合法 BFS 序

CF 的 EPIC August 考察了合法 DFS 序，想到今年北京市赛的合法 BFS 序（还没有补题），因此写了这篇总结。

定义：

• DFS 序 对一棵树进行 DFS 得到的节点序列，我们记 tdfn[i] 表示在时间$i$ 时的节点编号；
• dfn[u] (Depth First Number) 节点$u$ 在 DFS 序中的位置，即开始遍历$u$ 时的时间戳；
• dfnR[u] 节点$u$ 子树中的节点的最大 DFS 序，即结束遍历$u$ 时的时间戳。

DFS 序的暴力判法

虽然本题不允许暴力，暴力方法也与本题无关。。但为了文章的完整性

核心思想是，逐位匹配，当遍历到树的节点$u$ 和 DFS 序的第$i$ 位时：

• 如果$u$ 的是叶子节点，回溯；
• 如果 DFS 序的第$i+1$ 位是$u$ 的某个子节点，匹配成功，继续 DFS；
• 否则匹配失败，不是合法的 DFS 序。

void eachT() {
    int n = read();

    vector<unordered_map<int, int>> E(n+1);  // 为方便查询 用unordered_map代替vector存图
    for (int u = 2; u <= n; ++u) {
        int p = read();
        E[p][u] = 1;
    }

    for (int q = read(); q--; ) {
        vector<int> dfn(n+1), vis(n+1, 0);
        for (int i = 0; i < n; i++) {
            dfn[i] = read();
        }

        int id = 0, ok = true;
        auto dfs = [&](this auto&& self, int u) -> void {
            vis[u] = 1;
            int& v = dfn[i++d];
            if (E[u].count(v)) self(v);
            else if (!E[u].empty()) ok = false;
        };
        if (dfn[0] != 1) ok = false;
        else dfs(1);

        printf("%s\n", ok ? "Yes" : "No");
    }
}

这种方法适用于所有的 有向图，只需增加是否访问过，即：

• 如果$u$ 没有出边或者 所有出边指向的点已经访问过，回溯；
• 如果 DFS 序的第$i+1$ 位是$u$ 的某个子节点，匹配成功，记为已访问，继续 DFS；
• 否则匹配失败，不是合法的 DFS 序。

void eachT() {
    int n = read(), m = read();

    vector<unordered_map<int, int>> E(n);
    while (m--) {
        int u = read(), v = read();
        E[u][v] = 1;
    }

    for (int q = read(); q--; ) {
        vector<int> dfn(n+1), vis(n, 0);
        for (int i = 0; i < n; i++) {
            dfn[i] = read();
        }

        int id = 0, ok = true;
        auto dfs = [&](this auto&& self, int u) -> void {
            vis[u] = 1;
            int& v = dfn[i++d];
            if (E[u].count(v)) {
                self(v);
            }
            else for (auto& [v, _] : E[u]) {
                if (!vis[v]) ok = false;
            }
        };
        while (id < n) {
            int& u = dfn[id];
            if (!vis[u]) dfs(u);
        }

        printf("%s\n", ok ? "Yes" : "No");
    }
}

DFS 序的性质

1. tdfn[dfn[u]] = u, dfn[tdfn[u]] = u；
2. dfnR[u] = dfn[u] + siz[u] - 1；
3. 判断祖先必要条件 祖先先于后代遍历，即若 dfn[u] < dfn[v]，则$u$ 不在$v$ 的子树中，即$v$ 不是$u$ 的祖先；
4. 判断祖先充要条件$u$ 是$v$ 的祖先$\iff$ dfn[u] < dfn[v] <= dfnR[v] <= dfnR[u]；
5. DFS 序求 LCA 若$u \neq v$，则 LCA 为 DFS 序在区间 [dfn[u]+1, dfn[v]] 中深度最小的任意节点$r$ 的父亲，即 lca(u, v) = p[r]；
6. DFS 序相邻两点的性质 1 如果在性质 5 中取$u$ 和$v$ 为 DFS 序中相邻的两个节点，这时区间长度为$1$，节点$r$ 只能取$v$，因此 lca(u, v) = p[v]，这也是 DFS 序合法的充要条件；
7. DFS 序相邻两点的性质 2 相邻两点的距离再求和为两倍的边数，即$\sum d_{u,v}=2(n-1)$，其中$u$ 和$v$ 为 DFS 序中相邻的两个节点；
8. ……

CF2002D2. DFS Checker (Hard Version)

有了上面的性质 6，我们只需判断当前的 DFS 序是否满足这个条件。每次交换两个点，每个点只需和左右各判断一次。

void eachT() {
    int n = read(), q = read();
    for (int u = 2; u <= n; ++u) {
        p[u] = read();
        E[p[u]].push_back(u);
    }

    dfs(1);

    for (int i = 1; i <= n; i++) {
        tdfn[i] = read();
    }

    int res = 0;  // 合法总数
    vector<int> oks(n+1, 0);  // 记录DFS序的i位置是否合法
    auto check = [&](int i) {
        int& u = tdfn[i], & v = tdfn[i+1];
        res -= oks[i];
        oks[i] = i >= 1 && i < n && getlca(u, v) == p[v];
        res += ok;
    }; // 判断DFS序的i位置是否合法

    for (int i = 1; i < n; i++) {
        check(i);
    }

    while (q--) {
        int x = read(), y = read();
        swap(tdfn[x], tdfn[y]);

        check(x-1);
        check(x);
        check(y-1);
        check(y);

        printf("%s\n", res == n - 1 ? "YES" : "NO");
    }
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using ll = long long;
using pii = pair<int, int>;
using namespace std;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

const int N = 3e5 + 10;
int tdfn[N], p[N], dfn[N], siz[N];
vector<int> E[N];
void dfs(int u) {
    siz[u] = 1;
    for (auto& v : E[u]) {
        dfs(v);
        siz[u] += siz[v];
    }
}

void eachT() {
    int n = read(), q = read();
    for (int i = 0; i <= n; i++) {
        E[i].clear();
    }

    for (int u = 2; u <= n; u++) {
        p[u] = read();
        E[p[u]].push_back(u);
    }

    dfs(1);

    vector<set<pii>> Q(n + 1);
    for (int i = 1; i <= n; i++) {
        tdfn[i] = read();
        int u = tdfn[i];
        dfn[u] = i;
        Q[p[u]].insert({ i, siz[u] });
    }

    int res = 0;
    vector<int> oks(n + 1);
    auto check = [&](int i) {
        if (!i)return;
        if (Q[i].empty()) return;
        int mn = (*Q[i].begin()).first;
        int mx = (*Q[i].rbegin()).first, w = (*Q[i].rbegin()).second;
        res -= oks[i];
        oks[i] = dfn[i] != mn - 1 || mx <= dfn[i] || mx > dfn[i] + siz[i] - w;
        res += oks[i];
    };

    for (int i = 1; i <= n; i++) {
        check(i);
    }

    while (q--) {
        int x = read(), y = read();
        int u = tdfn[x], v = tdfn[y];

        Q[p[u]].erase({ dfn[u], siz[u] });
        Q[p[v]].erase({ dfn[v], siz[v] });

        swap(dfn[u], dfn[v]);
        swap(tdfn[x], tdfn[y]);

        Q[p[u]].insert({ dfn[u], siz[u] });
        Q[p[v]].insert({ dfn[v], siz[v] });

        check(p[u]);
        check(p[v]); 
        check(u);
        check(v);

        puts((res || tdfn[1] != 1) ? "NO" : "YES");
    }
}

int main() {
    for (int T = read(); T--; eachT());
    return 0;
}

出栈序列的合法性

void eachT() {
    int siz = read(), n = read(), q = read();
    while (q--) {
        stack<int> stk;
        int in = 1, ok = 1;
        for (int i = 1; i <= n; i++) {
            int out = read();
            while (stk.empty() || stk.top() != out) {
                if (in > n || stk.size() == siz) { ok = 0; break; }
                stk.push(in);
                in++;
            }
            stk.pop();
        }
        printf("%s\n", ok ? "YES" : "NO");
    }
}

树上并查集维护优化连边

例 1 有边权的树。求有序三元组$(i,j,k)$ 对数，满足：

• $i,j,k$ 是三个不同的点；
• $i$ 到$j$ 有路径，$i$ 到$k$ 也有路径；
• 每条路径中至少有一条幸运边（幸运边：边权是仅仅由$4$ 和$7$ 组成的正整数）。(Lucky Tree CF109C)

思路 将非幸运边缩成一个点，答案即是$\sum a_{i}(n-a_{i})(n-a_{i}+1)$。

auto judge = [&](int n) {
    while (n) {
        if (n % 10 != 4 && n % 10 != 7) return 0;
        n /= 10;
    }
    return 1;
};

int n;
cin >> n;

DSU dsu(n);
for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    if (!judge(w)) dsu.uno(u, v);
}

ll res = 0;
for (int i = 1; i <= n; i++) {
    if (dsu.find(i) == i) res += dsu.size(i) * C2(n - dsu.size(i));
}
cout << res << "\n";

例 2 给定一棵$n$ 个点的边权为$0$ 或$1$ 的树，一条合法的路径$(x,y)\ (x\neq y)$ 满足，从$x$ 走到$y$，一旦经过边权为$1$ 的边，就不能再经过边权为$0$ 的边。求有多少路径满足条件？(CF1156D. 0-1-Tree)

int n;
cin >> n;

vector dsu(2, DSU(n));
for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    dsu[w].uno(u, v);
}

ll res = 0;
for (int i = 0; i < n; i++) {
    res += 1ll * (dsu[1].size(i) - 1) * (dsu[0].size(i) - 1);
    if (dsu[1].find(i) == i) {
        res += 1ll * dsu[1].size(i) * (dsu[1].size(i) - 1);
    }
    if (dsu[0].find(i) == i) {
        res += 1ll * dsu[0].size(i) * (dsu[0].size(i) - 1);
    }            
}

cout << res << "\n";

2024 杭电多校 5005 - 树论（二）

[[…/contests/2024杭电多校/2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）#*5005 - 树论（二）|2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）]]

题意 树，将一条边删去后，设原树$G$ 被分成不连通的两棵树$G_1,G_2$，求$\max\limits_{x\in V_1,y\in V_2} \gcd(x,y)$。对每条边都询问。数据范围：$n \leqslant 10^{6}$。

Input	Output
3 1 2 2 3	1 1
4 1 2 2 3 2 4	1 1 2

思路 倒序枚举$\gcd$ 的值$d$，这两点间路径上的答案都是$d$，因为结果不再改变，我们将这路径上所有的点合并为一个点，用并查集维护。时间复杂度$\Theta(n\log n)$。

vector<pair<int, int>> E[N];
int p[N], dep[N], idx[N], ans[N];
void dfs(int u) {
    for (auto& [v, id] : E[u]) {
        if (v == p[u]) continue;
        dep[v] = dep[u] + 1;
        idx[v] = id;           // 边的性质嫁接到点上 见树基础
        p[v] = u;
        dfs(v);
    }
}

void eachT() {
    int n = read();

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].emplace_back(v, i);
        E[v].emplace_back(u, i);
    }

    dfs(1);

    DSU dsu(n);

    for (int d = n / 2; d >= 1; --d) {
        for (int j = d + d; j <= n; j += d) {
            int u = dsu.find(d), v = dsu.find(j);
            while (u != v) {
                if (dep[u] > dep[v]) swap(u, v);
                ans[idx[v]] = d;
                dsu.uno(p[v], v);    // 合并路径上所有点
                v = dsu.find(p[v]);  // 遍历路径上所有点
            }
        }
    }

    for (int i = 1; i < n; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
}

树上线段树合并

p-级表亲

题意 求森林中，节点$v$ 有多少个$p$-级表亲。(VJsum1E. Blood Cousins)

思路 某个节点的$p$-级表亲的深度相同，每次询问即$v$ 的$p$-级祖先的深度为$\text{dep}_{v}$ 的儿子个数。先离线存储询问，对于询问$v,p$，存储$p$-级祖先和$\text{dep}_{v}$（如果$p$-级祖先不存在，则不存储，此时答案是 0）。这样只需要统计每一个节点$u$ 对应的深度$\text{dep}$ 的答案，即查询$u$ 对应的权值线段树上从$\text{dep}$ 到$\text{dep}$ 的数量。

线段树维护（深度，每一深度的节点个数），单点加。

提示：

1. 题给的图是森林，可以创建一个虚拟的「超级爸爸」是每个树根的祖先，将森林化为一棵树。（警钟敲烂！新增节点会导致深度 +1，也会导致小于某个深度的节点总数 +1，不理解的看 CTSC1997 选课）
2. 求$v$ 的$p$-级祖先，类似于求 LCA，倍增向上跳。
3. 离线存储答案。

/// ----------------线段树----------------
struct info {
    int sum{ 0 };
    void apply(const info& d) {
        sum += d.sum;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum };
    }
};

/// ----------------树+LCA----------------
vector<int> E[N];
int p[N][22], dep[N];
void initlca(int u) {
    for (int i = 1; i <= __lg(dep[u]); i++)
        p[u][i] = p[p[u][i - 1]][i - 1];
    for (auto& v : E[u]) {
        if (v == p[u][0]) continue;
        dep[v] = dep[u] + 1;
        p[v][0] = u;
        initlca(v);
    }
}

// v的k级祖先
int jump(int v, int k) {
    k = dep[v] - k;
    if (k <= 0) return -1;
    while (dep[v] > k) v = p[v][__lg(dep[v] - k)];
    return v;
}

/// ----------------线段树合并----------------
vector<pair<int, int>> que[N];
int res[N];
SMT<info> smt;
int rt[N];
void dfs(int u) {
    smt.modify(dep[u], { 1 }, rt[u]);      // 把信息存进去
    for (auto v : E[u]) {
        dfs(v);                            // 先把子树的信息算好
        smt.merge(rt[u], rt[v]);           // 把子树的信息存到这个节点上
    }
    // 计算与这个节点相关的答案
    for (auto [depth, id] : que[u]) {
        res[id] = smt.query(depth, depth, rt[u]).sum - 1;
    }
}

/// ----------------主函数----------------
void eachT() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        int x = read();
        if (!x) x = n + 1;  // 给森林一个虚拟根节点n+1
        E[x].push_back(i);
    }
    initlca(n + 1);
    int q = read();
    for (int i = 1; i <= q; i++) {
        int v = read(), p = read();
        int fav = jump(v, p);                  // v的p级祖先
        if (fav == -1) res[i] = 0;               // v没有p级祖先 答案是0
        else que[fav].push_back({ dep[v],i });   // 存储每个询问
    }
    smt.init(0, n + 1);
    dfs(n + 1);  // 线段树合并 计算答案
    for (int i = 1; i <= q; i++) {
        printf("%d ", res[i]);
    }
}

子树颜色种类数

题意 一棵$n$ 个点以 1 为根的树，树上每个点有一个颜色。$m$ 次询问在这棵树中，以$x$ 为根的子树内，与$x$ 距离（定义为边数）不超过$k$ 的点中，一共出现了多少种不同的颜色。(VJsum1I. Colourful Tree)

思路 线段树维护（颜色，颜色的种类和数量）。其中颜色的种类对于叶节点即是 0 或 1，push_up 操作是相加；颜色的数量只用于计算叶子的颜色数是 0 还是 1，无需 push_up。

/// ----------------线段树----------------
struct info {
    int sum{ 0 };
    int cnt{ 0 };
    void apply(const info& d) {
        cnt += d.cnt;
        sum = cnt != 0;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum, l.cnt + r.cnt };
    }
};

/// ----------------树+LCA----------------
vector<int> E[N], ksons[N];
int p[N][22], dep[N];
int c[N];
void initlca(int u) {
    for (int i = 1; i <= __lg(dep[u]); i++) 
        p[u][i] = p[p[u][i - 1]][i - 1];
    for (auto& v : E[u]) {
        if (v == p[u][0]) continue;
        dep[v] = dep[u] + 1;
        p[v][0] = u;
        initlca(v);
    }
}
int jump(int v, int k) {
    k = dep[v] - k;
    if (k < 0) return -1;
    while (dep[v] > k) v = p[v][__lg(dep[v] - k)];
    return v;
} // v的k级祖先

/// ----------------线段树合并----------------
SMT<info> smt;
int rt[N], res[N];
void dfs(int u) {
    smt.modify(c[u], 1, rt[u]);         // 添加u的颜色
    for (auto& v : E[u]) {
        if (v == p[u][0]) continue;
        dfs(v);
        smt.merge(rt[u], rt[v]);
    }
    for (auto& c : ksons[u]) {
        smt.modify(c, -1, rt[u]);       // 删除u的k+1层儿子的颜色
    }
    res[u] = smt.query(smt.L, smt.R, rt[u]).sum; // 查询u的子树的颜色数
}

/// ----------------主函数----------------
void eachT() {
    int n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        c[i] = read();
    }
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    // 统计每个节点的k+1层儿子的颜色
    initlca(1);
    for (int i = 1; i <= n; i++) {
        int x = jump(i, k + 1);
        if (x != -1) ksons[x].push_back(c[i]);
    }
    smt.init(1, n);
    dfs(1);
    for (int q = read(); q--; ) {
        int x = read();
        printf("%d\n", res[x]);
    }
}

VJsum1L. Dominant Indices

题意 有根树，设$d(x,y)$ 表示$x$ 子树内到$x$ 距离为$y$ 的点的个数，对于每个$x$，求满足$d(x,y)$ 最大的最小的$y$。

思路 线段树维护（每个深度的点的个数，区间最大值及取到最大值的编号）。

/// ----------------线段树----------------
struct info {
    int mx{ 0 };
    int id{ 0 };
    void apply(const info& o)& {
        mx += o.mx;
        id = o.id;
    }
    friend info operator + (const info& l, const info& r) {
        if (l.mx >= r.mx) return l;
        else return r;
    }
};

/// ----------------线段树合并----------------
vector<int> E[N];
int dep[N];
SMT<info> smt;
int res[N];

void dfs(int u, int p) {
    smt.modify(dep[u], { 1, dep[u] }, u);
    for (auto& v : E[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        smt.merge(u, v);
    }
    res[u] = smt.query(dep[u], smt.R, u).id - dep[u];
}

/// ----------------主函数----------------
void eachT() {
    int n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    smt.init(0, n);
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", res[i]);
    }
}

2024 杭电多校 1003 - 树

[[…/contests/2024杭电多校/2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）|2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）]]

题意 给定一棵根为$1$ 的树，点$i$ 具有一个权值$A_i$。 定义：

• $f(u,v) = \max(A_u, A_v) \times |A_u - A_v|$
• $\operatorname{ans}_i = \sum_{u\in \operatorname{subtree}(i), v\in \operatorname{subtree}(i)} f(u,v)$
  求${\Large\oplus}_{i=1}^{n}(\operatorname{ans}_i \bmod 2^{64})$。

思路 由第一条联想到权值线段树，由第二条想到树上启发式合并。下面的代码其实是线段树合并和启发式合并的杂糅，想写线段树合并但引入了启发式，最终发现线段树合并是假的，本质是将线段树的编号进行传递。

将 info 开成线段树。由线段树的动态性，不必局限于 info 的增加和去除，动态开点可以天然地存储每一个节点的信息，也可以轻松地转移、修改。

/// ----------------线段树----------------
struct info {
    int siz{ 0 };
    ull sum{ 0 };
    ull sqr{ 0 };
    void apply(const info& d) {
        siz += d.siz;
        sum += d.sum;
        sqr += d.sqr;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.siz + r.siz, l.sum + r.sum, l.sqr + r.sqr };
    }
};

/// ----------------树+LCA----------------
vector<int> E[N];
int w[N], siz[N];
int unix, dfn[N], dfnR[N], tdfn[N];  // DFS树: 时间戳 DFS序 子树的最大DFS序 DFS序对应的节点编号
void init(int u, int p) {
    siz[u] = 1;
    dfn[u] = ++unix, tdfn[unix] = u;
    for (auto v : E[u]) {
        if (v == p) continue;
        init(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[E[u][0]]) swap(v, E[u][0]);
    }
    dfnR[u] = unix;
}

/// ----------------线段树合并----------------
SMT<info> smt;
int rt[N];
ull ans[N];

// 用v给u计算答案
void cal(int u, int v) {
    // 算小于w[v]的
    auto res = smt.query(smt.L, w[v] - 1, rt[u]);
    ans[u] += (ull)res.siz * w[v] * w[v] - w[v] * res.sum;

    // 算大于w[v]的
    res = smt.query(w[v] + 1, smt.R, rt[u]);
    ans[u] += (ull)res.sqr - w[v] * res.sum;
}

void dfs(int u, int p) {
    // 算重儿子
    if (E[u][0] != p) {
        int& v = E[u][0];
        dfs(v, u);
        ans[u] += ans[v];    // 把重儿子的答案传递给根
        rt[u] = rt[v];       // 把重儿子的信息全部转移给根
    }

    // 算轻儿子
    for (auto v : E[u]) {
        if (v == p || v == E[u][0]) continue;
        dfs(v, u);               // 先把子树的信息算好
        for (int i = dfn[v]; i <= dfnR[v]; i++) {
            int& v = tdfn[i];
            cal(u, v);
            smt.modify(w[v], { 1, (ull)w[v], (ull)w[v] * w[v] }, rt[u]);
        }  // 计算每一个轻儿子子树的信息 算一个存一个
    }

    cal(u, u);  // 计算根的信息
    smt.modify(w[u], { 1, (ull)w[u], (ull)w[u] * w[u] }, rt[u]);
}

/// ----------------主函数----------------
void eachT() {
    int n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        w[i] = read();
    }
    smt.init(0, 1e6);
    init(1, 0);
    dfs(1, 0);
    ull anss = 0;
    for (int i = 1; i <= n; i++) {
        anss ^= (2 * ans[i]);
    }
    printf("%llu\n", anss);
}

本题如果使用线段树合并，能省一个$\log$。

在此之前先化简，

$$\begin{aligned} f(u,v) &= \max(A_u, A_v) \times |A_u - A_v| \\ &= \operatorname{max}^{2} - \max\times\min \end{aligned}$$

因此，$\sum f(u,v)= \sum \operatorname{max}^{2}(A_{u},A_{v}) - \sum A_{u}A_{v}$，后一项是$\left( \sum A_{u} \right)^{2} - \sum A_{u}^{2}$，可以直接计算，前者用在权值线段树上计算。

线段树维护（点权，数量），$\sum \operatorname{max}^{2}(A_{u},A_{v})$ 中，每个$A_{u}^{2}$ 的系数是比它小的数的数量，合并两棵树增加的贡献是右子树的平方和乘上另一棵树的左子树的大小。

/// ----------------线段树----------------
struct info {
    int siz{ 0 };
    ull sqr{ 0 };
    void apply(const info& d) {
        siz += d.siz;
        sqr += d.sqr;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.siz + r.siz, l.sqr + r.sqr };
    }
};

template<class info>
void SMT<info>::merge(auto& res, int& q, int& p, int L, int R) {
    if (!q || !p) return q |= p, void();
    if (R - L < 2) {
        res += 2ull * t[q].siz * t[p].sqr;
        return t[q].apply(t[p]);
    }
    if (ls[q] && rs[p]) res += 2ull * t[ls[q]].siz * t[rs[p]].sqr;
    if (rs[q] && ls[p]) res += 2ull * t[ls[p]].siz * t[rs[q]].sqr;
    merge(res, ls[q], lson);
    merge(res, rs[q], rson);
    return push_up(q);
}

/// ----------------线段树合并----------------
vector<int> E[N];
int w[N];
SMT<info> smt;
ull sum1[N], sum2[N], ans[N];

void dfs(int u, int p) {
    smt.modify(w[u], { 1, (ull)w[u] * w[u] }, u);
    sum1[u] += (ull)w[u] * w[u];
    sum2[u] += w[u];
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        sum1[u] += sum1[v];
        sum2[u] += sum2[v];
        smt.merge(sum1[u], u, v);
    }
    ans[u] = sum1[u] - sum2[u] * sum2[u];
}

/// ----------------主函数----------------
void eachT() {
    int n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        w[i] = read();
    }
    smt.init(0, 1e6);
    dfs(1, 0);
    ull anss = 0;
    for (int i = 1; i <= n; i++) {
        anss ^= ans[i];
    }
    printf("%llu\n", anss);
}

2024 杭电多校 3002 - 旅行

[[…/contests/2024杭电多校/2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）|2024-07-26：2024“钉耙编程”中国大学生算法设计超级联赛（3）]]

求树上一些不相交的链使得权值和最大，每个链要求起始点和终止点颜色相同，权值为起点和终点的权值和。

树上 DP，可以在 LCA 处枚举经过这个点的链，如果这个点不被任何链经过，那么把所有孩子节点的 DP 值加起来，否则需要找一条经过 LCA 的链，假设为$(u,v)$，那么需要维护起来的权值有$u,v$ 下面的子树值和这条链上其他点的其他孩子的 dp 值。

用线段树合并可以解决，线段树的下标为颜色，把链上一串 DP 值维护起来，这样在合并的时候可以顺带 DP 出最优方案。

int c[N], v[N];
int L, R, rt[N];
int pcnt;
struct info {
    int mx;
    int mrk;    // 赋值标记
    int l, r;
} t[N << 5];

void init(int l, int r) {
    pcnt = 0;
    L = l, R = r;
}

void init(int p) {
    t[p] = { 0, 0, 0, 0 };
}

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

ll dp[N];
vector<int> E[N];

void push_up(info& p, info l, info r) {
    p.mx = max(l.mx, r.mx);
}
void push_down(info& p, int d, int l) {
    p.mx += d;
    p.mrk += d;
}

void push_up(int& p) { push_up(t[p], t[ls], t[rs]); }
void push_down(int p, int l) {
    if (t[p].mrk == 0) return;
    if (ls) push_down(t[ls], t[p].mrk, l - (l >> 1));
    if (rs) push_down(t[rs], t[p].mrk, l >> 1);
    t[p].mrk = 0;
}

int merge(int q, int& ans, int& p, int cl = L, int cr = R) {
    if (!q || !p) return q | p;
    if (cl == cr) {
        ans = max(ans, t[q].mx + t[p].mx);
        return push_up(t[q], t[q], t[p]), q;
    }
    push_down(q, len), push_down(p, len);
    t[q].l = merge(t[q].l, ans, lson);
    t[q].r = merge(t[q].r, ans, rson);
    return push_up(q), q;
}

// 单点赋值
void modify(int x, ll d, int& p, int cl = L, int cr = R) {
    if (!p) p = ++pcnt, init(p);
    if (cl == cr) return t[p].mx = d, void();
    if (x <= mid) modify(x, d, lson);
    else modify(x, d, rson);
    return push_up(p);
}
// 键是颜色 值是权值 维护不同颜色的权值最大值

void dfs(int u, int p) {
    dp[u] = 0;
    modify(c[u], v[u], rt[u]);
    int mx = 0;
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u] += dp[v];
        rt[u] = merge(rt[u], mx, rt[v]);
    }
    //modify(c[u], mx, rt[u]);
    t[rt[u]].mx -= mx;
    t[rt[u]].mrk -= mx;
    cerr << "\nt[rt[" << u << "]].mx = " << t[rt[u]].mx << endl; 
    dp[u] += mx;
    cerr << u << " " << "mx = " << mx << " dp = " << dp[u] << endl;
}

void eachT() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        c[i] = read();
        rt[i] = 0;
        E[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        v[i] = read();
    }

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }

    init(1, n);

    dfs(1, 0);

    printf("%lld\n", dp[1]);
}

重剖、启发式合并

状压

题意 一棵$n$ 个节点的根为$1$ 的树，每个节点上有一种颜色$c_i$。$m$ 次操作，操作有两种：
1. 将以$u$ 为根的子树上的所有节点的颜色改为$c$。
2. 询问以$u$ 为根的子树上的所有节点的颜色数量。

数据范围：$1 \leqslant n,m \leqslant 4\times 10^5$，$1 \leqslant c_i \leqslant 60$。(VJsum1H. New Year Tree)

思路 注意到颜色数只有 60，考虑 状压，如果有颜色 x，则存储 1ll<<x。问子树颜色种类，查询对应区间的按位或，颜色种类即是按位或后的 1 的个数。

线段树维护（状压的 60 种颜色，区间按位或），修改是区间赋值。

struct mark {
    ll asn{ -1 };
    void apply(const mark& d, int s) {
        if (~d.asn) asn = d.asn;
    }
};
struct info {
    ll val{ 0 };
    void apply(const mark& d, int s) {
        if (~d.asn) val = d.asn;
    }
    void apply(const info& d) {
        val |= d.val;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.val | r.val };
    }
};

void eachT() {
    int n = read(), q = read(), r = 1;

    for (int u = 1; u <= n; u++) {
        w[u] = 1ll << read();
    }

    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(r);
    top[r] = r, dfs2(r);

    SMT<info, mark> smt;
    smt.init(1, n);

    for (int i = 1; i <= n; i++) {
        smt.modify_node(i, { w[i] });
    }

    while (q--) {
        int op = read();
        if (op == 1) {
            ll u = read(), d = 1ll << read();
            smt.modify_subtree(u, { d });
        }
        else {
            int u = read();
            auto res = smt.query_subtree(u);
            printf("%d\n", __builtin_popcountll(res.val));
        }
    }
}

CF375D. Tree and Queries

有根树。在以 $u$ 为根的子树中，出现次数 $\geqslant k$ 的颜色有多少种。(2400)

int c[N];    // 颜色
int cnt[N];  // 每种颜色出现的次数
int sum[N];  // 出现次数大于等于k的颜色有多少种
vector<pair<int, int> > Q[N];
int Qns[N];

void add(int u) {
    cnt[c[u]] += 1;  // 这种颜色多一个
    sum[cnt[c[u]]] += 1;  // 这个数量的颜色多一个
}  // 增加u对info的影响

void del(int u) {
    sum[cnt[c[u]]] -= 1;
    cnt[c[u]] -= 1;
}  // 去除u对info的影响

void cal(int u) {
    for (auto& [k, id] : Q[u]) {
        Qns[id] = sum[k];
    }
}  // 利用info计算u的ans

CF600E. Lomsat gelral

有根树。在以 $u$ 为根的子树中，出现次数最多的颜色（可能有多个）占领$u$，求占领$u$ 的所有颜色的编号之和。(2300)

int c[N], cnt[N], maxsum;
ll sum, ans[N];

void add(int u) {
    int x = ++cnt[c[u]];
    if (x > maxsum) maxsum = x, sum = c[u];
    else if (x == maxsum) sum += c[u];
}  // 增加u对info的影响

void del(int u) {
    --cnt[c[u]];
    maxsum = sum = 0;  // 需要初始化
}  // 去除u对info的影响

void cal(int u) {
    ans[u] = sum;
}  // 利用info计算u的ans

树上数据结构

树上数颜色

vector<int> E[N];
int arr[N];
int p[N], dep[N], siz[N], top[N];
int efn[N], efnR[N], eseq[N], eunix;

void dfs(int u) {
    siz[u] = 1;
    for (auto& v : E[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dep[v] = dep[u] + 1;
        dfs(v);
        siz[u] += siz[v];
        if (siz[v] > siz[E[u][0]]) swap(v, E[u][0]);
    }
}

void dfs2(int u) {
    efn[u] = ++eunix, eseq[eunix] = u;
    for (auto& v : E[u]) {
        if (v == p[u]) continue;
        top[v] = v == E[u][0] ? top[u] : v;
        dfs2(v);
    }
    efnR[u] = ++eunix, eseq[eunix] = u;
}

// u,v的最近公共祖先
int getlca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) u = p[top[u]];
        else v = p[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}

int B;
struct QUE {
    int lca; // need lca or not
    int ql, qr, id;
    bool operator<(const QUE& b) const {
        return ql / B != b.ql / B ? ql < b.ql : (ql / B & 1 ? qr < b.qr : qr > b.qr);
    }
};

int cnt[N], now;  // 颜色数量
int cnt2[N];  // 每种颜色出现次数 偶数次不记
void add(int p) {   // p是欧拉序编号
    cnt2[eseq[p]]++;  // eseq[p]是树的编号
    if (cnt[arr[eseq[p]]] == 0) now++;
    cnt[arr[eseq[p]]] += cnt2[eseq[p]] & 1 ? 1 : -1;
    if (cnt[arr[eseq[p]]] == 0) now--;
}
void del(int p) {
    if (cnt[arr[eseq[p]]] == 0) now++;
    cnt2[eseq[p]]--;
    cnt[arr[eseq[p]]] -= cnt2[eseq[p]] & 1 ? -1 : 1;
    if (cnt[arr[eseq[p]]] == 0) now--;
}

void eachT() {
    int n = read();
    int q = read();
    B = sqrt(n);

    vector<int> alls;
    for (int i = 1; i <= n; i++) {
        arr[i] = read();
        alls.push_back(arr[i]);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (int i = 1; i <= n; i++) {
        arr[i] = lower_bound(alls.begin(), alls.end(), arr[i]) - alls.begin();
    }

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    top[1] = 1, dfs2(1);

    vector<QUE> que(q);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int u = read(), v = read();
        if (getlca(u, v) == u or getlca(u, v) == v) {
            if (getlca(u, v) == v) swap(u, v);
            que[i].ql = efn[u], que[i].qr = efn[v];
            que[i].lca = 0;
        }
        else {
            que[i].ql = efnR[u], que[i].qr = efn[v];
            que[i].lca = getlca(u, v);
        }
        que[i].id = i;
    }
    sort(que.begin(), que.end());

    int cl = 1, cr = 0;
    for (auto& [lca, ql, qr, id] : que) {
        while (cl > ql) add(--cl);
        while (cr < qr) add(++cr);
        while (cl < ql) del(cl++);
        while (cr > qr) del(cr--);
        if (lca) add(efn[lca]);
        ans[id] = now;
        if (lca) del(efn[lca]);
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", ans[i]);
    }
}

2024 杭电多校 5004 - 树论（一）

[[…/contests/2024杭电多校/2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）#*5004 - 树论（一）|2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）]]

题意 给定以$1$ 为根的树，节点标号$1\sim n$。$q$ 次询问，每次询问$r$ 的子树中，有多少节点对$(u,v)$ 满足$\operatorname{lcm}(u,v) \leqslant x$。数据范围：$n \leqslant 10^{5}$。

Input	Output
1 7 1 3 1 7 3 2 3 5 5 4 5 6 5 3 23 5 10 5 30 1 5 1 7	23 3 9 15 27

思路 暴力枚举 lcm。离线询问，按$x$ 升序处理，将点对$(u,v)$ 的贡献存储到$\operatorname{lca}$ 上，查询即为子树所有节点的贡献之和。

#include <iostream>
#include <algorithm>
#include <vector>
using pii = pair<int, int>;
using piii = tuple<int, int, int>;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return 1ll * a * b / gcd(a, b); }

constexpr int N = 1e5 + 8;
vector<int> divisor[N];
vector<pii> pairs[N];
void initlcm() {
    for (int i = 1; i < N; i++) {
        for (int L = i; L < N; L += i)
            divisor[L].emplace_back(i);
    }
    for (int i = 1; i < N; i++) {
        for (int L = i; L < N; L += i) {
            for (int& j : divisor[L]) {
                if (i >= j and lcm(i, j) == L)
                    pairs[L].emplace_back(i, j);
            }
        }
    }
}

vector<int> E[N];
int pa[N], hson[N], siz[N], dep[N], top[N];
int unix, dfn[N], dfnR[N], tdfn[N];

void dfs1(int u, int p = 0) {
    int mx = 0;
    dep[u] = dep[p] + 1;
    siz[u] = 1;
    dfn[u] = ++unix, tdfn[unix] = u;
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs1(v, u);
        pa[v] = u;
        siz[u] += siz[v];
        if (siz[v] > mx) hson[u] = v, mx = siz[v];
    }
    dfnR[u] = unix;
}

void dfs2(int u, int p = 0) {
    if (hson[u]) {
        top[hson[u]] = top[u];
        dfs2(hson[u], u);
    }
    for (auto& v : E[u]) {
        if (v == p || v == hson[u]) continue;
        top[v] = v;
        dfs2(v, u);
    }
}

int getlca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) u = pa[top[u]];
        else v = pa[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}

struct BIT {
    vector<int> t;
    int N;
    BIT(int n) {
        N = n + 1;
        t.resize(N);
    }
    void update(int p, int x) {
        while (p < N) t[p] += x, p += p & -p;
    }
    int query(int p) {
        int res = 0;
        while (p >= 1) res += t[p], p -= p & -p;
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

void eachT() {
    int n;
    cin >> n;

    unix = 0;
    for (int i = 0; i <= n; i++) {
        E[i].clear();
        pa[i] = hson[i] = siz[i] = dep[i] = top[i] = 0;
        dfn[i] = dfnR[i] = tdfn[i] = 0;
    }  // RE

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }

    dfs1(1);
    top[1] = 1, dfs2(1);

    int q;
    cin >> q;

    vector<piii> ask(q);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int r, x;
        cin >> r >> x;
        ask[i] = { x, r, i };
    }
    sort(ask.begin(), ask.end());  // 按 x 升序

    BIT bit(n);

    int it = 0;
    for (int L = 1; L < N; ++L) {
        for (auto& [u, v] : pairs[L]) {
            if (u > n or v > n) continue;
            bit.update(dfn[getlca(u, v)], u == v ? 1 : 2);
        }
        while (it < q) {
            auto& [x, r, id] = ask[it];
            if (x != L) break;
            ans[id] = bit.query(dfn[r], dfnR[r]);
            i++t;
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << " \n"[i == q - 1];
    }
}

int main() {
    ios::sync_with_stdio(palse);
    cin.tie(nullptr);
    cout.tie(nullptr);

    initlcm();

    int T;
    cin >> T;

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

    return 0;
}

2024 杭电多校 9002 - 树上询问

[[…/contests/2024杭电多校/2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）|2024-08-16：2024“钉耙编程”中国大学生算法设计超级联赛（9）]]

给定一个大小为$n$ 的树，第$i$ 个节点点权为$p_i$，其中$p_1,p_2,\ldots,p_n$ 是一个大小为$n$ 的排列。接下来你要处理$m$ 次以下两种操作之一：

• 给定树上两点$x$ 和$y$，交换$p_x$ 和$p_y$。
• 给定区间$[l,r]$，询问是否存在树上两点$x$ 和$y$，使得$x$ 到$y$ 路径上的点权恰好为$[l,r]$ 区间内所有整数。

vector<int> E[N];
int w[N];

int p[N], hson[N], dep[N], siz[N], top[N];
int dfn[N], dfnR[N], tdfn[N], dunix;
int L[N], R[N], eunix;
int tim[N];
void dfs(int u) {
    siz[u] = 1;
    dep[u] = dep[p[u]] + 1;
    L[u] = ++eunix, tim[eunix] = u;
    dfn[u] = ++dunix, tdfn[dunix] = u;
    for (auto& v : E[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]]) hson[u] = v;
    }
    R[u] = ++eunix, tim[eunix] = u;
    dfnR[u] = dunix;
}

void dfs2(int u) {
    if (hson[u]) {
        top[hson[u]] = top[u];
        dfs2(hson[u]);
    }
    for (auto& v : E[u]) {
        if (v == p[u] || v == hson[u]) continue;
        top[v] = v;
        dfs2(v);
    }
}

int getlca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) u = p[top[u]];
        else v = p[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}

struct SMT1 {
    int pcnt;
    static int L, R, rt;
    struct info {
        int Lmn, Lmx, Rmn, Rmx;
        int l, r;
    } t[N << 2];

    void init(int l, int r) {
        for (int i = 0; i <= pcnt; i++) init(i);
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(info& p, info l, info r) {
        p.Lmn = min(l.Lmn, r.Lmn);
        p.Lmx = max(l.Lmx, r.Lmx);
        p.Rmn = min(l.Rmn, r.Rmn);
        p.Rmx = max(l.Rmx, r.Rmx);
    }
    void push_up(int& p) { push_up(t[p], t[ls], t[rs]); }

    void modify(int x, auto d, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (cl == cr) {
            t[p].Lmn = t[p].Lmx = d.first;
            t[p].Rmn = t[p].Rmx = d.second;
            return;
        }
        if (x <= mid) modify(x, d, lson);
        if (mid < x)  modify(x, d, rson);
        return push_up(p);
    }

    info query(int l, int r, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }
};
int SMT1::L, SMT1::R, SMT1::rt;
SMT1 smt1;

struct SMT2 {
    int pcnt;
    static int L, R, rt;
    struct info {
        int mx, mn;
        int l, r;
    } t[N << 2];

    void init(int l, int r) {
        for (int i = 0; i <= pcnt; i++) init(i);
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(info& p, info l, info r) {
        p.mx = max(l.mx, r.mx);
        p.mn = min(l.mn, r.mn);
    }
    void push_up(int& p) { push_up(t[p], t[ls], t[rs]); }

    void modify(int x, int d, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (cl == cr) {
            t[p].mx = t[p].mn = d;
            return;
        }
        if (x <= mid) modify(x, d, lson);
        if (mid < x)  modify(x, d, rson);
        return push_up(p);
    }

    info query(int l, int r, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }

    info query_path(int u, int v) {
        info res = { 0, 1000000000 };
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                push_up(res, res, query(dfn[top[u]], dfn[u]));
                u = p[top[u]];
            }
            else {
                push_up(res, res, query(dfn[top[v]], dfn[v]));
                v = p[top[v]];
            }
        }
        if (dep[u] > dep[v]) {
            push_up(res, res, query(dfn[v], dfn[u]));
        }
        else {
            push_up(res, res, query(dfn[u], dfn[v]));
        }
        return res;
    }
};
int SMT2::L, SMT2::R, SMT2::rt;
SMT2 smt2;

void eachT() {
    int n = read();
    
    eunix = dunix = 0;
    for (int u = 1; u <= n; u++) {
        E[u].clear();
        L[u] = R[u] = tim[u] = 0;
        dfn[u] = dfnR[u] = tdfn[u] = 0;
        p[u] = hson[u] = dep[u] = siz[u] = top[u] = 0;

        w[u] = read();
    }

    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);
    top[1] = 1, dfs2(1);

    smt1.init(1, n);
    smt2.init(1, n);

    for (int u = 1; u <= n; u++) {
        smt1.modify(w[u], make_pair(L[u], R[u]));
        smt2.modify(dfn[u], w[u]);
    }

    int q = read();
    while (q--) {
        int op = read();
        if (op == 1) {
            int u = read(), v = read();  // 交换u和v的点权
            swap(w[u], w[v]);
            smt1.modify(w[u], make_pair(L[u], R[u]));
            smt1.modify(w[v], make_pair(L[v], R[v]));
            smt2.modify(dfn[u], w[u]);
            smt2.modify(dfn[v], w[v]);
        }
        else {
            int l = read(), r = read();
            auto res1 = smt1.query(l, r);
            int u = tim[res1.Lmx], v = tim[res1.Rmn];
            int lca = getlca(u, v);
            if (lca == u || lca == v) {
                u = tim[res1.Lmn], v = tim[res1.Lmx];
                lca = getlca(u, v);
            } 
            auto res2 = smt2.query_path(u, v);
            if (dep[u] + dep[v] - 2 * dep[lca] == r - l && res2.mx == r && res2.mn == l) {
                printf("Yes\n");
            }
            else {
                printf("No\n");
            }
        }
    }
}

signed main() {
    for (int T = read(); T--; eachT());
    return 0;
}

淀粉汁儿

k 距离点对儿

给定一棵有$n$ 个点的带边权的树，$q$ 次询问树上距离为$k$ 的点对儿是否存在。数据范围：$n\leqslant 10^4$，$q\leqslant 100$，$1 \leqslant k \leqslant 10^7$，$1 \leqslant w \leqslant 10^4$。

Input	Output
5 20 1 2 4 1 3 7 2 4 8 2 5 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	No No No Yes Yes No Yes Yes Yes No Yes Yes Yes No No Yes No No Yes No

树。$n$ 个节点。求树上路径长度等于$k$ 的数量。(1800, CF161D)
时间复杂度$\Theta(nk^{2})$，可利用主机派优化为$\Theta(nk)$，此外，点分治和长链剖分可实现更优秀的线性复杂度。

int k, dp[N][K];
ll ans = 0;
void dfs(int u, int p) {
    for (auto v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int i = 1; i <= k; i++) ans += dp[v][i - 1] * dp[u][k - i];
        for (int i = 1; i <= k; i++) dp[u][i] += dp[v][i - 1];
    }
    dp[u][0] = 1;
    ans += dp[u][k];
}
print(ans);

constexpr int K = 1e7 + 8;
int ans[K];
void TDC::cal(int u) {
    unordered_map<int, int> ttdeps;
    ttdeps[0] = 1;

    for (auto& [w, v] : E[u]) {
        if (vis[v]) continue;
        vector<int> deps;

        auto dfs = [&](this auto&& self, int u, int p, int dep) -> void {
            if (dep >= K) return;
            deps.push_back(dep);
            for (auto& [w, v] : E[u]) {
                if (v == p || vis[v]) continue;
                self(v, u, dep + w);
            }
        };

        dfs(v, u, w);

        for (auto& dep : deps) {
            for (auto& [k, v] : ttdeps) {
                if (dep + k >= K) continue;
                ans[dep + k] |= v;
            }
        }
        for (auto& dep : deps) {
            ttdeps[dep] = 1;
        }
    }
}

void eachT() {
    int n = read(), q = read();
    tdc.init(n);
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read(), w = read();
        tdc.add(u, v, w);
    }
    tdc.solve();
    while (q--) {
        int u = read();
        printf("%s\n", ans[u] ? "Yes" : "No");
    }
}

cal 函数的最坏复杂度为$\operatorname{O}(n^{2})$。注意到询问数只有 100，故离线处理询问，针对询问计算。

constexpr int K = 1e7 + 8;
vector<int> que, ans;
void TDC::cal(int u) {
    unordered_map<int, int> ttdeps;
    ttdeps[0] = 1;

    for (auto& [w, v] : E[u]) {
        if (vis[v]) continue;
        vector<int> deps;

        auto dfs = [&](this auto&& self, int u, int p, int dep) -> void {
            if (dep >= K) return;
            deps.push_back(dep);
            for (auto& [w, v] : E[u]) {
                if (v == p || vis[v]) continue;
                self(v, u, dep + w);
            }
        };

        dfs(v, u, w);

        for (int i = 0; i < que.size(); i++) {
            if (ans[i]) continue;          // 剪枝 避免TLE
            for (auto& dep : deps) {
                if (ttdeps.count(que[i] - dep)) {
                    ans[i] = 1;
                }
            }
        }
        for (auto& dep : deps) {
            ttdeps[dep] = 1;
        }
    }
}

void eachT() {
    int n = read(), q = read();
    tdc.init(n);
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read(), w = read();
        tdc.add(u, v, w);
    }
    que.resize(q), ans.resize(q);
    for (int i = 0; i < q; i++) {
        que[i] = read();
    }
    tdc.solve();
    for (int i = 0; i < q; i++) {
        printf("%s\n", ans[i] ? "Yes" : "No");
    }
}

最小化边数的$k$ 距离点对儿

int k, ans;
void TDC::cal(int u) {
    unordered_map<int, int> ttdeps;
    ttdeps[0] = 0;   // WA

    for (auto& [w, v] : E[u]) {
        if (vis[v]) continue;
        unordered_map<int, int> deps;

        auto dfs = [&](this auto&& self, int u, int p, int dep, int len) -> void {
            if (dep > k) return;
            if (!deps.count(dep) || deps[dep] > len) {
                deps[dep] = len;
            }
            for (auto& [w, v] : E[u]) {
                if (v == p || vis[v]) continue;
                self(v, u, dep + w, len + 1);
            }
        }; 

        dfs(v, u, w, 1);

        for (auto& [dep, len] : deps) {
            if (ttdeps.count(k - dep)) {
                ans = min(ans, ttdeps[k - dep] + len);
            }
        }
        for (auto& [dep, len] : deps) {
            if (!ttdeps.count(dep) || ttdeps[dep] > len) {
                ttdeps[dep] = len;
            }
        }
    }
}

void eachT() {
    int n = read();
    k = read();
    tdc.init(n);
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read(), w = read();
        tdc.add(u, v, w);
    }
    ans = inf;
    tdc.solve();
    if (ans == inf) ans = -1;
    printf("%d\n", ans);
}

≤ k 距离点对儿

给定一棵$n$ 个节点的有边权的树，求出树上两点距离小于等于$k$ 的点对儿数量。数据范围：$n\leqslant 4\times 10^4$，$0\leqslant w\leqslant 10^3$，$0\leqslant k\leqslant 2\times 10^4$。

Input	Output
7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2 10	5

int k;
ll ans;
void TDC::cal(int u) {
    bit.init();
    bit.update(1, 1);

    for (auto& [w, v] : E[u]) {
        if (vis[v]) continue;

        vector<int> deps;

        auto dfs = [&](this auto&& self, int u, int p, int dep) -> void {
            if (dep > k) return;
            deps.push_back(dep);
            for (auto& [w, v] : E[u]) {
                if (v == p || vis[v]) continue;
                self(v, u, dep + w);
            }
        };

        dfs(v, u, w);

        for (auto& dep : deps) {
            ans += bit.query(k - dep + 1);
        }
        for (auto& dep : deps) {
            bit.update(dep + 1, 1);
        }
    }
}

void eachT() {
    int n = read();
    tdc.init(n);
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read(), w = read();
        tdc.add(u, v, w);
    }
    k = read();
    ans = 0;
    tdc.solve();
    printf("%lld\n", ans);
}

GCD Counting

给出一棵树，树有点权，最大化链上所有点的点权的$\gcd>1$ 的链长。

对重心分解质因数，按树直径的想法向下找最长链和次长链。

int val[N];
int ans;
void TDC::cal(int u) {
    auto solve = [&](int x, int u) {
        auto dfs = [&](this auto&& self, int x, int u, int p) -> int {
            int res = 1;
            for (auto& [w, v] : E[u]) {
                if (v == p || vis[v]) continue;
                if (val[v] % x) continue;  // 如果v点的值不是x的倍数
                res = max(res, self(x, v, u) + 1);
            }
            return res;
        };

        // 找两个最大的dp
        int mx1 = 0, mx2 = 0;
        for (auto& [w, v] : E[u]) {
            if (vis[v]) continue;
            if (val[v] % x) continue; // 如果v点的值不是x的倍数
            int res = dfs(x, v, u);
            if (res > mx1) mx2 = mx1, mx1 = res;
            else if (res > mx2) mx2 = res;
        }
        ans = max(ans, mx1 + mx2 + 1);
    };

    auto tmp = val[u];
    for (int i = 2; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            solve(i, u);
            while (tmp % i == 0) tmp /= i;
        }
    }
    if (tmp > 1) solve(tmp, u);
}

void eachT() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        val[i] = read();
    }
    tdc.init(n);
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        tdc.add(u, v, 1);
    }
    tdc.solve();
    printf("%d\n", ans);
}

树上倍增（树上二分）与差分

模板 2：树上倍增（树上二分）与差分

题意 树，根为 1，有边权有点权。问对于每个顶点 $u$，子树中有多少个顶点 $v$ 满足 $\text{d}(v, u) \leqslant w_v$。数据范围：$n \leqslant 2\times10^{5},\ w \leqslant 10^{9}$。(CF739B)

思路 1 线段树秒了，但秒 T。

思路 2 正难则反，对于每一个点$v$ 有多少个顶点满足$u$ 是$v$ 的祖先且 $\text{d}(v, u) \leqslant w_v$。显然，对于$v$ 的祖先节点$u$ 从低到高的 $\text{d}(v, u)$ 满足单调性，对于某一个顶点$v$，可选择 二分 或 倍增，找到它的祖先节点中最后一个满足 $\text{d}(v, u) \leqslant w_v$ 的$u$，那么$u$ 到$v$ 中所有的点都符合题意，答案都需要 +1，用 树上差分 优化。

vector<pair<int, int>> E[N];
ll sum[N][D];
int p[N][D];
int w[N], ans[N];

void dfs(int u) {
    for (auto& [w, v] : E[u]) {
        p[v][0] = u;
        sum[v][0] = w;
        dfs(v);
    }
}

void dfs2(int u) {
    for (auto& [w, v] : E[u]) {
        dfs2(v);
        ans[u] += ans[v];
    }
}

void eachT() {
    int n = read();

    for (int u = 1; u <= n; ++u) {
        w[u] = read();
    }

    for (int u = 2; u <= n; ++u) {
        int p = read(), w = read();
        E[p].emplace_back(w, u);
    }

    dfs(1);

    for (int d = 1; d < D; ++d) {
        for (int u = 1; u <= n; ++u) {
            p[u][d] = p[p[u][d - 1]][d - 1];
            sum[u][d] = sum[u][d - 1] + sum[p[u][d - 1]][d - 1];
        }
    }

    for (int v = 1; v <= n; ++v) {
        int u = v, val = w[v];

        for (int d = D - 1; d >= 0; --d) {
            if (val >= sum[u][d]) {
                val -= sum[u][d];
                u = p[u][d];
            }
        }

        --ans[p[u][0]];
        ++ans[p[v][0]];
    }

    dfs2(1);

    for (int u = 1; u <= n; ++u) {
        printf("%d ", ans[u]);
    }
}

初始有一棵只有根节点的树，根编号为$0$，根有价值$p_0$ 和数量$w_0$。
在$q$ 个操作中：

• 操作1：新增一个未出现过的节点$u$，令节点$u$ 与某已经存在的节点$v$ 相连，有价值$p_u$ 和数量$w_u$，保证$p_u < p_v$；
• 操作2：进行一次询问，给定节点$k$ 和背包容量$s$，在从节点$k$ 到根的路径上的每个点取走一部分（即选择一个$m_v$，更新$w_v = w_v - m_v$），取出的数量之和不超过$s$。最大化$Ans = \sum(m_v \times p_v)$，输出$\sum m_v$ 和$Ans$，注意每次询问过后，需要进行更新$w_v = w_v - m_v$；
• 操作3：给定一个节点$l$，将$w_l$ 置为$0$。(2024 杭电多校 5010 - 世末农庄 [[…/contests/2024杭电多校/2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）|2024-08-02：2024“钉耙编程”中国大学生算法设计超级联赛（5）]])

思路 由于总是保证$p_u < p_v$，最优策略是从根开始取，沿着路径一步步尽可能多地取。每次从根遍历是不现实的，用树上倍增找出起始点的分界线。复杂度$\Theta(q\log n)$。

void eachT() {
    int n;
    cin >> n;
    ++n;
    vector<int> w1(n), w2(n);
    vector p(n, vector<int>(D + 1));
    cin >> w1[0] >> w2[0];

    for (int i = 1; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int u, v;
            cin >> u >> v;
            cin >> w1[u] >> w2[u];
            p[u][0] = v;
            for (int i = 1; i <= D; i++) {
                p[u][i] = p[p[u][i - 1]][i - 1];
            }
        }
        else if (op == 2) {
            int k, s;
            cin >> k >> s;
            ll res1 = 0, res2 = 0;
            while (s > 0 && w2[k] != -1) {
                int u = k;
                for (int i = D; ~i; --i) {
                    if (w2[p[u][i]] != -1) {
                        u = p[u][i];
                    }
                }

                int buy = min(s, w2[u]);
                s -= buy;
                w2[u] -= buy;
                if (w2[u] == 0) {
                    w2[u] = -1;
                }
                res1 += buy;
                res2 += 1ll * buy * w1[u];
            }
            cout << res1 << ' ' << res2 << '\n';
        }
        else {
            int l;
            cin >> l;
            w2[l] = 0;
        }
    }
}

树基础

浮点数权值的精度丢失

题意 给定一棵树，每次询问给出两个整数$x,y$，表示询问树上以$x$ 和$y$ 为端点的简单路径上边权乘积与点$x$ 的点权相乘是否为整数。(VJspr11C - 一切都已过去)

思路 如果两个非零浮点数相乘得到整数，这两个数必然具有形式$\cfrac{p}{2^{\alpha}5^{\beta}}$，将浮点数转化为整数，避免精度丢失。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 8;
struct node {
    int cnt2, cnt5, num0;  // 小数点后有多少个2 5 
    node operator+(const node& b) const {
        return { cnt2 + b.cnt2, cnt5 + b.cnt5, num0 + b.num0 };
    }
};
vector<pair<node, int> > E[N];
int Log2[N], p[N][22], dep[N];
node val[N], wpos[N];

void dfs(int u) {
    for (int i = 1; i <= Log2[dep[u]]; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for (auto& [w, v] : E[u]) {
        if (v == p[u][0]) continue;
        dep[v] = dep[u] + 1;
        p[v][0] = u;
        val[v] = val[u] + w;  // 将边权存储在子节点上
        dfs(v);
    }
}

int getlca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);                            // -> dep[u]<=dep[v]
    while (dep[u] != dep[v]) v = p[v][Log2[dep[v] - dep[u]]];   // -> dep[u]==dep[v]
    if (u == v) return u;
    for (int d = Log2[dep[u]]; d >= 0; --d) {
        if (p[u][d] != p[v][d]) u = p[u][d], v = p[v][d];
    }  // 一步一步向上跳
    return p[u][0];
}

int main() {
    for (int i = 2; i < N; i++) Log2[i] = Log2[i >> 1] + 1;

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        int cnt2 = 0, cnt5 = 0;
        while (x && x % 2 == 0) x /= 2, cnt2 += 1;
        while (x && x % 5 == 0) x /= 5, cnt5 += 1;
        node w = { cnt2,cnt5,!x };
        wpos[i] = w;
    }

    for (int i = 2; i <= n; i++) {
        int u, v;
        double wd;
        cin >> u >> v >> wd;

        int fz = (int)(wd * 10000), fm = 10000; // 分子分母
        int cnt2 = 0, cnt5 = 0;
        while (fz && fz % 2 == 0) fz /= 2, cnt2 += 1;
        while (fz && fz % 5 == 0) fz /= 5, cnt5 += 1;
        while (fm && fm % 2 == 0) fm /= 2, cnt2 -= 1;
        while (fm && fm % 5 == 0) fm /= 5, cnt5 -= 1;

        node w = { cnt2,cnt5,!fz };
        E[u].push_back({ w,v });
        E[v].push_back({ w,u });
    }

    dfs(1);

    while (q--) {
        int u, v;
        cin >> u >> v;
        bool flag = wpos[u].num0 == 1
            || val[u].num0 + val[v].num0 - val[getlca(u, v)].num0 * 2 > 0
            || val[u].cnt2 + val[v].cnt2 - val[getlca(u, v)].cnt2 * 2 + wpos[u].cnt2 >= 0
            && val[u].cnt5 + val[v].cnt5 - val[getlca(u, v)].cnt5 * 2 + wpos[u].cnt5 >= 0;
        cout << (flag ? "Yes" : "No") << '\n';
    }

    return 0;
}