- DL24JP 的博客
NOI 算法5 树上问题
-
DL24JP @ 2026-10-9 16:41:12
1.树链剖分
-
洛谷题目：P3379
-
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N−1 行每行包含两个正整数 x,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M 行每行包含两个正整数 a,b，表示询问 a 结点和 b 结点的最近公共祖先。
输出格式
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例
输入 #1复制
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
输出 #1复制
4 4 1 4 4
说明/提示
对于 30% 的数据，N≤10，M≤10。
对于 70% 的数据，N≤10000，M≤10000。
对于 100% 的数据，1≤N,M≤5×105，1≤x,y,a,b≤N，不保证 a=b。
-
-
重链 / 重儿子定义：
-
重儿子：节点的所有子节点中，子树大小最大的那个子节点（son[u]）。
-
重链：由父节点和重儿子依次连接形成的路径（轻儿子作为新重链的起点）。
-
-
LCA 求解逻辑：
-
若两个节点不在同一条重链上，将链头深度更大的节点跳转到其链头的父节点；
-
重复上述步骤直到两个节点在同一条重链上，此时深度更小的节点即为 LCA。
-
-
时间复杂度：
-
两次 DFS 的时间复杂度为 O (n)；
-
单次 LCA 查询的跳转次数为 O (log n)（树的高度），m 次查询总复杂度为 O (m log n)。
-
应用树链剖分可以求 LCA，也可在此基础上扩展为树链剖分的区间修改 / 查询（如维护树上路径和、路径最大值等）。
参考代码
// 树链剖分模板（用于求解LCA），时间复杂度 O(m log n)
// 核心思想：将树划分为若干条"重链"，通过链头快速跳转求解最近公共祖先（LCA）
#include<bits/stdc++.h>
using namespace std;
// 常量定义：树的最大节点数（根据题目需求调整，此处为5e5级别）
const int N = 500010;
// 全局变量说明
int n, m, s; // n:节点数 m:查询次数 s:树的根节点
int a, b; // 临时变量，用于读入边/查询的两个节点
vector<int> e[N]; // 邻接表，存储树的无向边
// 树链剖分核心数组
int fa[N]; // fa[u]：节点u的父节点
int son[N]; // son[u]：节点u的"重儿子"（子树大小最大的子节点）
int dep[N]; // dep[u]：节点u的深度（根节点深度为1）
int siz[N]; // siz[u]：以u为根的子树的节点总数
int top[N]; // top[u]：节点u所在"重链"的链头（链中深度最小的节点）
// 第一次DFS：初始化fa、dep、siz、son（重儿子）
// u：当前遍历的节点 f：当前节点的父节点
void dfs1(int u, int f)
{
fa[u] = f; // 记录u的父节点为f
dep[u] = dep[f] + 1; // u的深度 = 父节点深度 + 1（根的父是0，dep[0]=0）
siz[u] = 1; // 初始子树大小为1（仅包含自身）
// 遍历u的所有邻接节点
for (int v : e[u])
{
if (v == f) continue; // 跳过父节点，避免回环
dfs1(v, u); // 递归遍历子节点v，父节点为u
// 回溯时更新子树大小：u的子树大小 += 子节点v的子树大小
siz[u] += siz[v];
// 选择重儿子：如果v的子树大小大于当前重儿子的子树大小，则更新son[u]
if (siz[son[u]] < siz[v])
son[u] = v;
}
}
// 第二次DFS：初始化top（链头），划分重链
// u：当前遍历的节点 t：当前重链的链头
void dfs2(int u, int t)
{
top[u] = t; // 记录u所在重链的链头为t
// 优先遍历重儿子：重儿子与父节点属于同一条重链，链头不变
if (son[u])
dfs2(son[u], t);
// 遍历轻儿子：轻儿子作为新重链的链头（每条轻儿子对应一条新重链）
for (int v : e[u])
{
// 跳过父节点和重儿子（已处理）
if (v == fa[u] || v == son[u])
continue;
dfs2(v, v); // 轻儿子v的链头是自身
}
}
// 树链剖分求LCA（最近公共祖先）
// u、v：需要查询LCA的两个节点
int lca(int u, int v)
{
// 核心逻辑：将u和v不断跳转到所在重链的链头，直到二者在同一条重链上
while (top[u] != top[v])
{
// 始终让深度更大的链头对应的节点上跳（减少跳转次数）
if (dep[top[u]] < dep[top[v]])
swap(u, v);
// 将u跳转到其链头的父节点（相当于"跨过"当前重链，向上移动）
u = fa[top[u]];
}
// 当u和v在同一条重链上时，深度更小的节点就是LCA
return dep[u] < dep[v] ? u : v;
}
int main()
{
// 读入节点数、查询次数、根节点
scanf("%d%d%d", &n, &m, &s);
// 读入n-1条树边（树的边数=节点数-1）
for (int i = 1; i < n; i++)
{
scanf("%d%d", &a, &b);
e[a].push_back(b); // 无向边，双向存入邻接表
e[b].push_back(a);
}
// 执行两次DFS，完成树链剖分的初始化
dfs1(s, 0); // 第一次DFS：根节点s，父节点为0（虚拟节点）
dfs2(s, s); // 第二次DFS：根节点s的链头是自身
// 处理m次LCA查询
while (m--)
{
scanf("%d%d", &a, &b); // 读入查询的两个节点
printf("%d\n", lca(a, b)); // 输出LCA结果
}
return 0;
}
2.点分治
-
洛谷题目：P3806
-
题目描述
给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。
输入格式
第一行两个数 n,m。
第 2 到第 n 行，每行三个整数 u,v,w，代表树上存在一条连接 u 和 v 边权为 w 的路径。
接下来 m 行，每行一个整数 k，代表一次询问。
输出格式
对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。
输入输出样例
输入 #1复制
2 1 1 2 2 2输出 #1复制
AYE说明/提示
数据规模与约定
-
对于 30% 的数据，保证 n≤100。
-
对于 60% 的数据，保证 n≤1000，m≤50 。
-
对于 100% 的数据，保证 1≤n≤104，1≤m≤100，1≤k≤107，1≤u,v≤n，1≤w≤104。
-
-
解决的问题：
- 给定一棵带权无向树，多次询问某个数值 k，判断树上是否存在一条路径的长度恰好等于 k。最终输出每个询问的结果（AYE 表示存在，NAY 表示不存在）。
-
重心的作用：
点分治选择「重心」作为分治中心，是因为重心的最大子树大小最小，能保证递归深度为 O(log n)，避免退化为链时的 O(n) 深度，保证总时间复杂度为 O(n log n)。
-
calc 函数的核心思想：
-
对于当前重心 u，所有经过 u 的路径可拆分为：u 到子树 A 节点的路径 + u 到子树 B 节点的路径（A≠B）。
-
先统计一个子树的所有节点到 u 的距离，再用这些距离去匹配「已统计的距离」，判断是否能组成询问值（即 dis1 + dis2 = ask[k]）。
-
用 judge 数组标记已统计的距离，避免重复计算同一子树内的路径（同一子树的路径拼接会绕回，不是简单路径）。
-
-
关键细节：
-
del 数组标记已处理的重心，避免重复处理；
-
每次处理完一个重心的所有子树后，清空 judge 数组，防止影响下一轮分治；
-
两次调用 getroot：第一次找重心，第二次重构子树大小（确保后续分治的 siz 数组准确）。
-
-
时间复杂度：
每次找重心和处理路径的时间为 O(n)，递归深度为 O(log n)，总时间复杂度为 O(n log n + m n)（若 m 较大，可优化为用哈希 / 桶统计距离，将 m 的复杂度降为 O(m)）。
参考代码
#include<bits/stdc++.h>
using namespace std;
// 常量定义
const int N = 10005; // 树的最大节点数
const int INF = 10000005; // 距离上限（大于所有可能的路径长度）
// 邻接表结构体：存储树的边（链式前向星）
struct node
{
int v, w, ne; // v: 边的终点 w: 边的权值 ne: 下一条边的索引
} e[N << 1]; // 无向树，边数是2*(n-1)，所以开2倍空间
// 全局变量说明
int h[N], idx; // h[]: 链式前向星头节点 idx: 边的索引计数器（加边用）
// 点分治核心变量（找重心用）
int del[N]; // del[u]=1 表示节点u已作为重心处理过（被"删除"），不再参与后续分治
int siz[N]; // siz[u] 表示以u为根的子树大小（仅考虑未被删除的节点）
int mxs; // 记录当前节点的最大子树大小（用于判断重心）
int sum; // 当前待处理子树的总节点数
int root; // 当前待处理子树的重心
// 距离相关变量
int dis[N]; // 临时存储某棵子树中所有节点到重心的距离
int d[N]; // d[u] 表示节点u到当前重心的距离（递归求距离时用）
int cnt; // dis数组的有效长度（子树节点数）
// 查询相关变量
int ans[N]; // ans[i] 标记第i个询问是否有解（1=存在，0=不存在）
int q[INF]; // 临时存储需要清空的距离值（用于重置judge数组）
int judge[INF]; // judge[x]=1 表示当前已统计的路径中存在长度为x的路径
int n, m; // n: 节点数 m: 询问次数
int ask[N]; // 存储m个询问的目标长度
// 链式前向星加边函数
// u: 边的起点 v: 边的终点 w: 边的权值
void add(int u, int v, int w)
{
e[++idx].v = v; // 记录终点
e[idx].w = w; // 记录权值
e[idx].ne = h[u]; // 指向当前u的上一条边
h[u] = idx; // 更新u的头节点为当前边的索引
}
// 第一次DFS：寻找当前子树的重心
// u: 当前遍历节点 fa: 父节点（避免回环）
// 重心定义：删除该节点后，所有子树的大小的最大值最小
void getroot(int u, int fa)
{
siz[u] = 1; // 初始子树大小为1（仅自身，未被删除）
int s = 0; // 记录u的最大子树大小（子节点的子树）
// 遍历u的所有邻边
for (int i = h[u]; i; i = e[i].ne)
{
int v = e[i].v;
// 跳过父节点 或 已被删除的节点（已处理过的重心）
if (v == fa || del[v]) continue;
getroot(v, u); // 递归遍历子节点v
siz[u] += siz[v]; // 回溯更新子树大小
s = max(s, siz[v]); // 更新最大子树大小
}
// 补充：父节点方向的子树大小 = 总大小sum - 当前子树大小siz[u]
s = max(s, sum - siz[u]);
// 如果当前节点的最大子树大小小于全局最小值mxs，更新重心
if (s < mxs) mxs = s, root = u;
}
// 第二次DFS：计算子树中所有节点到当前重心的距离
// u: 当前遍历节点 fa: 父节点（当前重心）
void getdis(int u, int fa)
{
dis[++cnt] = d[u]; // 记录u到重心的距离到dis数组
// 遍历u的所有邻边
for (int i = h[u]; i; i = e[i].ne)
{
int v = e[i].v;
// 跳过父节点 或 已被删除的节点
if (v == fa || del[v]) continue;
d[v] = d[u] + e[i].w; // 计算v到重心的距离（父节点距离+边权）
getdis(v, u); // 递归遍历子节点v
}
}
// 核心函数：处理经过当前重心root的所有路径
// u: 当前分治的重心
void calc(int u)
{
judge[0] = 1; // 初始化：距离0存在（重心自身到自身的路径）
int p = 0; // 记录本次需要清空的距离数量（q数组的指针）
// 遍历重心u的所有邻边，处理每个子树
for (int i = h[u]; i; i = e[i].ne)
{
int v = e[i].v;
if (del[v]) continue; // 跳过已删除的节点
// 第一步：计算子树v中所有节点到重心u的距离
cnt = 0; // 重置dis数组长度
d[v] = e[i].w; // 子树v的根节点到u的距离 = 边权
getdis(v, u); // 递归获取子树v所有节点到u的距离，存入dis
// 第二步：检查当前子树的距离能否和已统计的距离组成询问值
// 枚举当前子树的所有距离dis[j]
for (int j = 1; j <= cnt; ++j)
{
// 枚举所有询问k
for (int k = 1; k <= m; ++k)
{
// 若询问值ask[k] >= 当前距离dis[j]，且存在距离为ask[k]-dis[j]
// 则说明存在两条路径（dis[j] 和 ask[k]-dis[j]）拼接成ask[k]
if (ask[k] >= dis[j])
ans[k] |= judge[ask[k] - dis[j]]; // 按位或，标记有解
}
}
// 第三步：将当前子树的距离加入judge数组（供后续子树使用）
for (int j = 1; j <= cnt; ++j)
{
if (dis[j] < INF) // 仅记录有效距离
{
q[++p] = dis[j]; // 记录需要清空的距离
judge[q[p]] = 1; // 标记该距离存在
}
}
}
// 第四步：清空本次统计的距离（避免影响后续分治）
for (int i = 1; i <= p; ++i)
judge[q[i]] = 0;
}
// 点分治主函数：递归处理每个子树
// u: 当前子树的重心
void divide(int u)
{
// 第一步：处理经过重心u的所有路径
calc(u);
// 第二步：标记u为已处理（删除），避免重复计算
del[u] = 1;
// 第三步：递归处理u的所有子树
for (int i = h[u]; i; i = e[i].ne)
{
int v = e[i].v;
if (del[v]) continue; // 跳过已删除的节点
// 重新计算子树v的重心：
mxs = sum = siz[v]; // 子树总大小为siz[v]，重置最大子树大小
getroot(v, 0); // 找子树v的重心
getroot(root, 0); // 重构子树大小（确保siz数组准确）
divide(root); // 递归处理子树的重心
}
}
int main()
{
// 第一步：读入树的节点数n和询问次数m
scanf("%d%d", &n, &m);
// 第二步：读入n-1条无向边，构建链式前向星
for (int i = 1; i < n; ++i)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w); // 加u->v的边
add(v, u, w); // 加v->u的边（无向树）
}
// 第三步：读入m个询问的目标长度
for (int i = 1; i <= m; ++i)
scanf("%d", &ask[i]);
// 第四步：初始化找整棵树的重心
mxs = sum = n; // 总节点数为n，重置最大子树大小
getroot(1, 0); // 第一次找重心（初始根为1）
getroot(root, 0); // 重构子树大小（确保siz数组准确）
// 第五步：启动点分治
divide(root);
// 第六步：输出每个询问的结果
for (int i = 1; i <= m; ++i)
ans[i] ? puts("AYE") : puts("NAY"); // 1=AYE（存在），0=NAY（不存在）
return 0;
}
3.虚树
-
洛谷题目：P2495 消耗战
-
题目描述
在一场战争中，战场由 n 个岛屿和 n−1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 1 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 k 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 1 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 m 次，所以我们只需要把每次任务完成即可。
输入格式
第一行一个整数 n，表示岛屿数量。
接下来 n−1 行，每行三个整数 u,v,w ，表示 u 号岛屿和 v 号岛屿由一条代价为 w 的桥梁直接相连。
第 n+1 行，一个整数 m ，代表敌方机器能使用的次数。
接下来 m 行，第 i 行一个整数 ki ，代表第 i 次后，有 ki 个岛屿资源丰富。接下来 ki 个整数 h1,h2,...,hki ，表示资源丰富岛屿的编号。
输出格式
输出共 m 行，表示每次任务的最小代价。
输入输出样例
输入 #1复制
10 1 5 13 1 9 6 2 1 19 2 4 8 2 3 91 5 6 8 7 5 4 7 8 31 10 7 9 3 2 10 6 4 5 7 8 3 3 9 4 6输出 #1复制
12 32 22说明/提示
数据规模与约定
-
对于 10% 的数据，n≤10,m≤5 。
-
对于 20% 的数据，n≤100,m≤100,1≤ki≤10 。
-
对于 40% 的数据，n≤1000,1≤ki≤15 。
-
对于 100% 的数据，2≤n≤2.5×105,1≤m≤5×105,∑ki≤5×105,1≤ki<n,hi=1,1≤u,v≤n,1≤w≤105 。
-
-
问题归纳：
- 此问题需要结合树上倍增（求 LCA）、虚树（压缩树结构）、树形 DP（求解最优值） 三大核心算法，解决的问题是：给定一棵带边权的无向树，多次查询 k 个关键点，求将这些关键点与根节点（1 号节点）连通的最小代价（代价规则：路径上的最小边权，最终取所有必要路径的最小总代价）。核心优化思路：通过虚树压缩原树结构（仅保留关键点和 LCA），再在虚树上做树形 DP，大幅降低多次查询的时间复杂度。
-
- 树上倍增预处理
-
预处理 fa[x][i] 数组，实现 O(log n) 时间求 LCA，是虚树构建的基础；
-
预处理 mn[x] 数组，记录根到 x 的最小边权，是 DP 的核心状态。
2. 虚树构建核心
-
按 DFS 序排序关键点，保证栈维护的是 “从根到当前节点的链”；
-
用栈维护虚树的节点，通过 LCA 合并不同分支，仅保留关键点和必要的 LCA，将原树的 O(n) 节点压缩为 O(k) 节点（k 为关键点数量），大幅降低 DP 的时间开销。
3. 树形 DP 状态转移
-
对于虚树的叶子节点（关键点）：必须连通到根，代价为 mn[x]（根到 x 的最小边权）；
-
对于虚树的非叶子节点：有两种选择：
-
汇总所有子节点的 DP 值（子树内关键点各自连通的总代价）；
-
直接取 mn[x]（当前节点到根的最小边权，覆盖所有子树关键点的连通需求）；
-
-
最终取两种选择的较小值，即为当前子树的最小连通代价。
4. 时间复杂度
-
原树预处理：O(n log n)；
-
单次查询：虚树构建 O(k log k)（排序） + DP O(k)；
-
总复杂度：O(n log n + m k log k)，远优于直接在原树上做 DP 的 O(m n)。
参考代码
// 核心算法：树上倍增（求LCA） + 虚树（压缩树形） + 树形DP（计算最小代价）
// 功能：处理多组查询，每组查询给定k个关键点，求覆盖这些关键点的最小代价
// 代价规则：关键点需连到根，非关键点可合并子树代价或选自身到根的最小边权（取更小）
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 250005; // 节点数上限（2.5e5）
int h[N], tot; // h[]：邻接表表头（复用：先存原树，后存虚树）；tot：邻接表边计数
// 邻接表边结构体
struct edge
{
int x, y, w, ne; // x/y：边的两个端点；w：边权；ne：下一条边的索引（邻接表链表）
} e[N << 1]; // 原树是无向树，边数2*(n-1)，开2倍空间
// 邻接表加边函数（无向边需调用两次）
// x/y：边的两个端点；w：边权
void add(int x, int y, int w)
{
e[++tot] = {x, y, w, h[x]}; // 新建边，ne指向当前x的表头
h[x] = tot; // 更新x的表头为新边的索引
}
// 树上倍增相关变量
int dep[N]; // dep[x]：节点x的深度（根1深度为1）
int fa[N][20]; // fa[x][i]：x的2^i级祖先（i∈[0,19]，覆盖2^19>2.5e5）
int siz[N]; // siz[x]：x的子树大小（本代码未实际使用）
int dfn[N], cnt; // dfn[x]：x的DFS序；cnt：DFS序计数器（虚树排序用）
int s[N], top; // s[]：构建虚树的栈；top：栈顶指针
int n, m, k, a[N]; // n：原树节点数；m：查询数；k：单次查询的关键点数量；a[]：存储单次查询的关键点
int vis[N]; // vis[x]=1表示x是当前查询的关键点，DP后重置为0
LL mn[N]; // mn[x]：根（1）到x路径上的最小边权
// 预处理DFS：初始化深度、倍增数组、DFS序、mn数组、子树大小
// x：当前节点；f：x的父节点
void dfs(int x, int f)
{
dfn[x] = ++cnt; // 记录x的DFS序
dep[x] = dep[f] + 1; // x的深度=父节点深度+1
fa[x][0] = f; // x的2^0=1级祖先就是父节点f
siz[x] = 1; // 子树大小初始化为1（仅自身）
// 构建倍增数组：fa[x][i] = fa[fa[x][i-1]][i-1]
for (int i = 1; i <= 19; i++)
{
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
// 遍历x的所有邻边（原树邻接表）
for (int i = h[x]; i; i = e[i].ne)
{
int y = e[i].y; // 邻接节点y
if (y == f) continue; // 跳过父节点，避免回边
// 计算y的mn值：根到y的最小边权 = min(根到x的最小边权, x-y的边权)
mn[y] = min(mn[x], (LL) e[i].w);
dfs(y, x); // 递归处理子节点y
siz[x] += siz[y]; // 更新x的子树大小（累加子节点y的子树大小）
}
}
// 树上倍增求x和y的最近公共祖先（LCA）
int lca(int x, int y)
{
// 保证x的深度≥y的深度，方便后续上跳
if (dep[x] < dep[y]) swap(x, y);
// 第一步：将x上跳至与y同一深度
for (int i = 19; ~i; i--)
{
// 从2^19到2^0枚举
if (dep[fa[x][i]] >= dep[y])
{
x = fa[x][i];
}
}
if (x == y) return y; // 深度相同后若x=y，直接返回LCA
// 第二步：x和y同步上跳，直到父节点相同
for (int i = 19; ~i; i--)
{
if (fa[x][i] != fa[y][i])
{
// 祖先不同时才上跳
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0]; // 最终父节点即为LCA
}
// 排序比较函数：按节点的DFS序升序排列（虚树构建的前提）
int cmp(int a, int b)
{
return dfn[a] < dfn[b];
}
// 构建虚树：仅保留关键点和必要的LCA，压缩树形规模
void build()
{
// 第一步：将关键点按DFS序排序，保证栈的处理顺序符合树形结构
sort(a + 1, a + k + 1, cmp);
tot = 0; // 重置边计数器（虚树复用tot和h数组）
s[top = 1] = 1; // 栈初始化：根节点1入栈
s[++top] = a[1]; // 第一个关键点入栈
// 遍历剩余关键点，构建虚树
for (int i = 2; i <= k; i++)
{
int l = lca(s[top], a[i]); // 栈顶节点与当前关键点的LCA
// 情况1：栈顶的上一个节点深度≥LCA深度 → 弹出栈顶并连边
while (top > 1 && dep[s[top - 1]] >= dep[l])
{
add(s[top - 1], s[top], 0); // 虚树连边（边权无意义，设为0）
top--;
}
// 情况2：LCA≠栈顶节点 → 连LCA与栈顶，弹出栈顶，LCA入栈
if (l != s[top])
{
add(l, s[top], 0);
s[top] = l;
}
// 当前关键点入栈
s[++top] = a[i];
}
// 处理栈中剩余节点，完成虚树连边
while (top > 1)
{
add(s[top - 1], s[top], 0);
top--;
}
}
// 树形DP：计算虚树上以x为根的子树的最小代价
// 返回值：x子树的最小代价
LL DP(int x)
{
if (vis[x])
{
// 情况1：x是当前查询的关键点
// 递归处理x的所有虚树子节点
for (int i = h[x]; i; i = e[i].ne)
{
DP(e[i].y);
vis[e[i].y] = 0; // 处理完子节点后重置vis标记
}
h[x] = 0; // 清空x的虚树邻接表（避免干扰下次查询）
return mn[x]; // 关键点代价=根到x的最小边权
}
else
{
// 情况2：x不是关键点
LL sum = 0; // 累加所有子树的代价和
for (int i = h[x]; i; i = e[i].ne)
{
sum += DP(e[i].y);
vis[e[i].y] = 0; // 重置子节点vis标记
}
h[x] = 0; // 清空x的虚树邻接表
// 非关键点代价：min(子树代价和, 根到x的最小边权)
return min(sum, mn[x]);
}
}
int main()
{
// 第一步：读入原树结构
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z); // 无向边：x→y
add(y, x, z); // 无向边：y→x
}
// 第二步：预处理（DFS初始化倍增、mn等）
mn[1] = 2e18; // 根节点无父边，mn设为极大值
dfs(1, 0); // 根节点1，父节点0（无）
memset(h + 1, 0, n << 2); // 清空原树邻接表（h数组复用为虚树）
// 第三步：处理多组查询
scanf("%d", &m);
while (m--)
{
scanf("%d", &k);
// 读入k个关键点，标记vis=1
for (int i = 1; i <= k; i++)
{
scanf("%d", &a[i]);
vis[a[i]] = 1;
}
build(); // 构建当前查询的虚树
printf("%lld\n", DP(1)); // DP计算根1的最小代价并输出
}
return 0;
}
4.动态树LCT
-
洛谷题目：P3690 动态树
-
问题描述
-
给定 n 个点以及每个点的权值，要你处理接下来的 m 个操作。 操作有四种，操作从 0 到 3 编号。点从 1 到 n 编号。
-
0 x y 代表询问从 x 到 y 的路径上的点的权值的 xor 和。保证 x 到 y 是联通的。
-
1 x y 代表连接 x 到 y，若 x 到 y 已经联通则无需连接。
-
2 x y 代表删除边 (x,y)，不保证边 (x,y) 存在。
-
3 x y 代表将点 x 上的权值变成 y。
输入格式
第一行两个整数，分别为 n 和 m，代表点数和操作数。
接下来 n 行，每行一个整数，第 (i+1) 行的整数 ai 表示节点 i 的权值。
接下来 m 行，每行三个整数，分别代表操作类型和操作所需的量。
输出格式
对于每一个 0 号操作，你须输出一行一个整数，表示 x 到 y 的路径上点权的 xor 和。
输入输出样例
输入 #1复制
3 3 1 2 3 1 1 2 0 1 2 0 1 1输出 #1复制
3 1输入 #2复制
5 14 114 514 19 19 810 1 1 2 0 1 2 2 1 2 1 1 2 1 2 3 2 1 3 1 1 3 1 4 5 1 2 5 0 3 5 0 3 4 3 5 233333 0 1 5 0 2 5输出 #2复制
624 315 296 232709 232823说明/提示
数据规模与约定
对于全部的测试点，保证：
-
1≤n≤105，1≤m≤3×105，1≤ai≤109。
-
对于操作 0,1,2，保证 1≤x,y≤n。
-
对于操作 3，保证 1≤x≤n，1≤y≤109。
-
-
1. Link-Cut Tree 的核心概念
-
实链 / 虚链：实链是显式用 Splay 维护的路径（父节点的指针在 Splay 中），虚链是原树的边但不在 Splay 中（父节点指针仅记录原树关系）；
-
Access 操作：核心基础，将任意节点到根的路径转为实链，是所有路径操作的前提；
-
Makeroot 操作：通过翻转路径实现换根，让任意节点成为原树的根，方便处理 “任意两点间路径”；
-
懒标记：翻转标记延迟处理，避免每次翻转都遍历路径，保证效率。
-
LCT 的核心思想是通过Splay 树维护树的 “实链”（显式路径），将原树的路径操作转化为 Splay 的区间操作，实现均摊 O (log n) 的时间复杂度。
2. 关键操作的逻辑链路
-
路径查询（output）：makeroot(x) → access(y) → splay(y) → y 的 sum 即为 x 到 y 的路径异或和；
-
连边（link）：makeroot(x) 后，若 x 和 y 不连通，将 x 的父设为 y；
-
断边（cut）：makeroot(x) 后，验证 x 和 y 直接相连，清空 y 的父节点；
-
单点修改（change）：将 x 伸展到 Splay 根，直接修改权值并上传 sum。
3. 时间复杂度
所有操作的均摊时间复杂度为 O (log n)，核心是 Splay 的伸展操作保证了均摊对数级别的访问次数，懒标记则避免了重复处理路径信息。
4. 注意事项
-
pushall 必须在 Splay 操作前执行，否则懒标记未下传会导致 sum 计算错误；
-
notroot 宏是判断节点是否为所在 Splay 的根，而非原树的根；
-
翻转标记仅影响 Splay 的左右孩子，不改变原树的父节点关系。
参考代码
#include <bits/stdc++.h>
using namespace std;
// 常量与宏定义：简化代码书写，提升可读性
#define N 100010 // 树的最大节点数
#define fa(x) tr[x].fa // 节点x的父节点（Splay树/原树共用）
#define lc(x) tr[x].ch[0] // 节点x的左孩子（Splay树中，对应实链的“下一级”）
#define rc(x) tr[x].ch[1] // 节点x的右孩子（Splay树中，对应实链的“上一级”）
#define notroot(x) lc(fa(x))==x||rc(fa(x))==x // 判断x是否是其所在Splay树的根（非根返回true）
int n, m; // n：节点总数；m：操作次数
// LCT节点结构体（每个节点对应Splay树节点+原树节点的信息）
struct node
{
int ch[2]; // ch[0]=左孩子，ch[1]=右孩子（Splay树结构）
int fa; // 父节点（Splay树和原树共用该指针）
int v; // 节点自身的权值
int sum; // 以x为根的Splay子树对应的路径异或和（核心维护的信息）
int tag; // 翻转懒标记（用于makeroot操作，标记路径需要翻转方向）
} tr[N];
// 【上传操作】更新当前节点的sum（异或和）
// 原理：当前节点的异或和 = 左子树异或和 ^ 自身权值 ^ 右子树异或和
void pushup(int x)
{
tr[x].sum = tr[lc(x)].sum ^ tr[x].v ^ tr[rc(x)].sum;
}
// 【下传操作】处理当前节点的翻转懒标记
// 原理：翻转标记生效时，交换左右孩子（对应路径方向翻转），并将标记下传给子节点
void pushdown(int x)
{
if (tr[x].tag) // 若当前节点有翻转标记
{
swap(lc(x), rc(x)); // 交换左右孩子（翻转路径方向）
tr[lc(x)].tag ^= 1; // 左孩子标记取反（后续需处理）
tr[rc(x)].tag ^= 1; // 右孩子标记取反
tr[x].tag = 0; // 清空当前节点标记
}
}
// 【递归下传】从x的所有祖先开始，逐层下传懒标记
// 作用：保证Splay操作前，路径上所有节点的标记都已生效（避免信息错误）
void pushall(int x)
{
if (notroot(x)) // 若x不是所在Splay的根，先处理父节点的标记
pushall(fa(x));
pushdown(x); // 处理当前节点的标记
}
// 【Splay旋转操作】将x绕其父节点y旋转，保持Splay的中序遍历对应原路径
// 旋转类型：根据x是y的左/右孩子，分为左旋/右旋
void rotate(int x)
{
int y = fa(x), z = fa(y); // y是x的父，z是y的父
int k = rc(y) == x; // k=1表示x是y的右孩子（右旋），k=0表示左孩子（左旋）
// 步骤1：处理z与x的连接（若y不是Splay根，更新z的孩子为x）
if (notroot(y))
tr[z].ch[rc(z) == y] = x;
fa(x) = z; // x的父节点更新为z
// 步骤2：处理x的异侧孩子与y的连接（k^1表示异侧：右→左，左→右）
tr[y].ch[k] = tr[x].ch[k ^ 1];
if (tr[x].ch[k ^ 1]) // 若x的异侧孩子存在，更新其父节点为y
fa(tr[x].ch[k ^ 1]) = y;
// 步骤3：将y设为x的异侧孩子，更新父节点
tr[x].ch[k ^ 1] = y;
fa(y) = x;
// 步骤4：自底向上更新sum（先更新y，再更新x）
pushup(y);
pushup(x);
}
// 【Splay伸展操作】将x伸展到其所在Splay树的根
// 核心规则：折线型先旋x，直线型先旋y，最终旋x（保证均摊复杂度）
void splay(int x)
{
pushall(x); // 先下传所有祖先的标记，保证操作前信息正确
while (notroot(x)) // 直到x成为Splay根
{
int y = fa(x), z = fa(y);
// 若y也不是Splay根：判断是折线（旋x）还是直线（旋y）
if (notroot(y))
(rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);
rotate(x); // 最终旋x到父节点位置
}
}
// 【Access操作】打通x到原树根的实链（将路径转为Splay的实链）
// 原理：从x向上遍历，将每个节点的右孩子替换为前一个节点，形成连续实链
void access(int x)
{
for (int y = 0; x; ) // y记录上一个处理的节点，初始为0（空）
{
splay(x); // 将x转到当前Splay的根（方便修改右孩子）
rc(x) = y; //** x的右孩子设为y（连接前后实链），一箭双雕，x-y建实链，x与另一个自然成虚链 **
pushup(x); // 更新x的sum（右孩子变化）
y = x; //** 记录当前节点为下一轮的y **
x = fa(x); //** x向上跳到父节点，继续处理 **
}
}
// 【Makeroot操作】将x设为原树的根
// 原理：先access(x)打通x到原根的实链，再splay(x)到根，最后翻转路径（交换左右孩子）
void makeroot(int x)
{
access(x); // 打通x到原根的实链
splay(x); // 将x伸展到Splay根（此时x是实链的末端）
tr[x].tag ^= 1; // 翻转标记（路径方向反转，x变为根）
}
// 【Split操作】拆分出x到y的路径，使其成为独立的Splay树（根为y）
// 原理：makeroot(x)将x设为根，access(y)打通x到y的实链，splay(y)到根
void split(int x, int y)
{
makeroot(x); // x设为原树根
access(y); // 打通x到y的实链
splay(y); // y伸展到Splay根（此时y的sum即为x到y的路径异或和）
}
// 【查询操作】输出x到y路径的异或和
void output(int x, int y)
{
split(x, y); // 拆分出x到y的路径
printf("%d\n", tr[y].sum); // y的sum即为路径异或和
}
// 【找根操作】查找x所在原树的根节点（用于判断连通性）
int findroot(int x)
{
access(x); // 打通x到原根的实链
splay(x); // x伸展到Splay根
// 一直向左走（实链的最底端），找到原树的根
while (lc(x))
{
pushdown(x); // 下传标记（避免左孩子错误）
x = lc(x);
}
splay(x); // 伸展根节点（防止后续操作卡链，优化复杂度）
return x;
}
// 【连边操作】连接x和y（保证x和y不连通时才连边）
void link(int x, int y)
{
makeroot(x); // x设为原树根
// 若x和y不在同一棵树（根不同），则将x的父节点设为y
if (findroot(y) != x)
fa(x) = y;
}
// 【断边操作】切断x和y之间的边（保证边存在时才断边）
void cut(int x, int y)
{
makeroot(x); // x设为原树根
// 断边条件：y的根是x && y的父是x && y没有左孩子（x和y直接相连）
if (findroot(y) == x && fa(y) == x && !lc(y))
{
fa(y) = 0; // 清空y的父节点（断边）
pushup(x); // 更新x的sum（右孩子y被移除）
}
}
// 【修改操作】修改节点x的权值为y
void change(int x, int y)
{
splay(x); // x伸展到Splay根（保证能直接修改）
tr[x].v = y; // 更新节点权值
pushup(x); // 上传sum（权值变化）
}
int main()
{
scanf("%d%d", &n, &m); // 读入节点数n，操作次数m
int t, x, y; // t：操作类型；x,y：操作参数
// 初始化每个节点的权值（sum初始等于v，因为无孩子）
for (int i = 1; i <= n; i++)
scanf("%d", &tr[i].v);
while (m--) // 处理m次操作
{
scanf("%d%d%d", &t, &x, &y);
if (t == 0) // 操作0：查询x到y路径的异或和
output(x, y);
else if (t == 1) // 操作1：连接x和y
link(x, y);
else if (t == 2) // 操作2：切断x和y之间的边
cut(x, y);
else // 操作3：修改节点x的权值为y
change(x, y);
}
return 0;
}