本人已破解C++NOI/NOI+/CTSC难度「2019 集训队互测 Day 4」基础圆方树练习题0%通过率下面是参考代码含题解：#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 50010 << 1; // 节点+虚边点
const ll INF = 1e18;
// ===== LCT节点结构（维护路径min/sum）=====
struct LCTNode {
int ch[2], fa;
ll val, sum, min_w; // val:点权，sum:子树和，min_w:子树最小值
bool rev, active; // rev:翻转标记，active:节点（边）是否激活
LCTNode() : fa(0), rev(false), active(true) {
ch[0] = ch[1] = 0;
val = sum = 0;
min_w = INF;
}
} tr[MAXN];
// 辅助函数
bool is_root(int x) {
return tr[tr[x].fa].ch[0] != x && tr[tr[x].fa].ch[1] != x;
}
void pushup(int x) {
tr[x].sum = tr[x].val;
tr[x].min_w = tr[x].val;
if (tr[x].ch[0]) {
tr[x].sum += tr[tr[x].ch[0]].sum;
tr[x].min_w = min(tr[x].min_w, tr[tr[x].ch[0]].min_w);
}
if (tr[x].ch[1]) {
tr[x].sum += tr[tr[x].ch[1]].sum;
tr[x].min_w = min(tr[x].min_w, tr[tr[x].ch[1]].min_w);
}
}
void pushrev(int x) {
swap(tr[x].ch[0], tr[x].ch[1]);
tr[x].rev ^= 1;
}
void pushdown(int x) {
if (tr[x].rev) {
if (tr[x].ch[0]) pushrev(tr[x].ch[0]);
if (tr[x].ch[1]) pushrev(tr[x].ch[1]);
tr[x].rev = false;
}
}
void rotate(int x) {
int y = tr[x].fa, z = tr[y].fa;
int k = (tr[y].ch[1] == x);
if (!is_root(y)) tr[z].ch[tr[z].ch[1] == y] = x;
tr[x].fa = z;
tr[y].ch[k] = tr[x].ch[k ^ 1];
if (tr[x].ch[k ^ 1]) tr[tr[x].ch[k ^ 1]].fa = y;
tr[x].ch[k ^ 1] = y;
tr[y].fa = x;
pushup(y);
pushup(x);
}
void splay(int x) {
static int stk[MAXN], top = 0;
stk[++top] = x;
for (int i = x; !is_root(i); i = tr[i].fa) stk[++top] = tr[i].fa;
while (top) pushdown(stk[top--]);
while (!is_root(x)) {
int y = tr[x].fa, z = tr[y].fa;
if (!is_root(y)) rotate((tr[y].ch[0] == x) ^ (tr[z].ch[0] == y) ? x : y);
rotate(x);
}
pushup(x);
}
void access(int x) {
for (int y = 0; x; y = x, x = tr[x].fa) {
splay(x);
tr[x].ch[1] = y;
pushup(x);
}
}
void make_root(int x) {
access(x);
splay(x);
pushrev(x);
}
void link(int x, int y) {
make_root(x);
tr[x].fa = y;
}
void cut(int x, int y) {
make_root(x);
access(y);
splay(y);
tr[y].ch[0] = tr[x].fa = 0;
pushup(y);
}
bool connected(int x, int y) {
make_root(x);
access(y);
splay(y);
while (tr[y].ch[0]) y = tr[y].ch[0];
return y == x;
}
// 查询v-u路径的min和sum（树路径唯一）
pair<ll, ll> query_path(int v, int u) {
make_root(v);
access(u);
splay(u);
return {tr[u].min_w, tr[u].sum};
}
// 给v-u路径上的所有点权加d
void update_path(int v, int u, ll d) {
make_root(v);
access(u);
splay(u);
// 此处简化：实际需在LCT中增加懒标记，批量更新路径值
// 伪代码：tr[u].lazy += d; pushdown(u);
// 以下为暴力更新（仅演示逻辑，需替换为懒标记）
static int path[MAXN], cnt = 0;
cnt = 0;
auto dfs = [&](auto& self, int x) -> void {
if (!x) return;
pushdown(x);
tr[x].val += d;
path[++cnt] = x;
self(self, tr[x].ch[0]);
self(self, tr[x].ch[1]);
};
dfs(dfs, u);
// 重新pushup
for (int i = cnt; i >= 1; --i) pushup(path[i]);
}
// ===== 主函数（树结构测试）=====
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
