登录
← 返回首页 | 代码片段 › 4 树上问题 › 树上问题 / 搜索
JSON MD

4 树上问题

含 48 个代码片段
最近公共祖先 lca 4.4.1 最近公共祖先LCA
73 行
CPP JSON
【最近公共祖先(LCA)——倍增法(Binary Lifting)】 ▪ dfs(u, p) — 预处理 DFS:计算 depth[u](深度),parent[u][0]=p(父节点),递推 parent[u][k] = parent[parent[u][k-1]][k-1](2^k 级祖先),并建立子节点列表 ch[u] ▪ lca(u, v) — 查询 LCA: ① 将较深的 u 上提到与 v 同深度(从高到低枚举 k,若 depth[u]-(1<<k)≥depth[v] 则跳) ② 若 u==v 返回;否则从高到低同时上跳(parent[u][k]!=parent[v][k] 时跳) ③ 最终 parent[u][0] 即为 LCA 预处理 O(N log N),单次查询 O(log N)。适用于树上距离、路径信息查询、树上差分。
C++ 73 行 CPP
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1e5 + 5;
const int LOG = 20;  // 2^20 > 1e5

vector<int> adj[MAXN];
vector<int> ch[MAXN];
int depth[MAXN];
int parent[MAXN][LOG];
int n, m, root;

// 预处理:计算每个节点的深度和2^k级祖先
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    parent[u][0] = p;
    for (int k = 1; k < LOG; ++k) {
        parent[u][k] = parent[parent[u][k-1]][k-1];
    }
    for (int v : adj[u]) {
        if (v != p) {
            ch[u].push_back(v);
            dfs(v, u);
        }
    }
}

// 查找u和v的最近公共祖先
int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    // 将u提到与v同一深度
    for (int k = LOG - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = parent[u][k];
        }
    }
    if (u == v) {
        return u;
    }
    // 同时向上跳
    for (int k = LOG - 1; k >= 0; --k) {
        if (parent[u][k] != parent[v][k]) {
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    return parent[u][0];
}

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

    cin >> n >> m;
    root = 1;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 预处理
    dfs(root, 0);

    // lca查询
    // cout << lca(u, v);
    return 0;
}
树链剖分+MOD shulianpoufenMOD 4.4.2 树链剖分
219 行
CPP JSON
【树链剖分(Heavy-Light Decomposition)——带 MOD 版】 ▪ dfs1(u, p) — 第一次 DFS:计算 parent、depth、sz(子树大小)、heavy(重儿子) ▪ dfs2(u, h) — 第二次 DFS:分配 pos(线段树位置/DFS 序)、top(重链顶部),优先遍历重儿子保证重链连续 ▪ build(datas, tree, rt, l, r) — 线段树建树,O(N) ▪ pushDown(tree, rt, len) — 下传懒标记,O(1) ▪ query(tree, rt, l, r, ql, qr) — 线段树区间查询(含 MOD),O(log N) ▪ updateRange(tree, rt, l, r, ul, ur, val) — 线段树区间更新(含 MOD),O(log N) ▪ queryPath(u, v) — 查询树上路径 u↔v 的权值和:反复跳深度较深的 top,每次跳 O(log N),总计 O(log² N) ▪ updatePath(u, v, val) — 更新树上路径 u↔v 的权值,同理 O(log² N) 剖分 O(N),每次路径/子树操作 O(log² N)。适用于树上路径权值修改/查询(含取模)。
C++ 219 行 CPP
const int MAXN = 1e5 + 5;  // 最大节点数
int N, M, R, P;  // 节点数、操作数、根节点、模数
vector<int> adj[MAXN];  // 邻接表存储树结构
int val[MAXN];  // 节点初始权值

// 树链剖分相关变量
int parent[MAXN];  // 父节点
int depth[MAXN];   // 节点深度
int sz[MAXN];      // 子树大小
int heavy[MAXN];   // 重儿子
int pos[MAXN];     // 节点在线段树中的位置
int top[MAXN];     // 所在重链的顶部节点
int current_pos;   // 当前DFS序位置

// 线段树节点结构
struct node {
    int data;  // 节点值
    int lazy;  // 懒标记
    node() : data(0), lazy(0) {}
};

vector<node> tree;  // 线段树

// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
    if (left == right) {
        tree[rt].data = datas[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(datas, tree, 2 * rt, left, mid);
    build(datas, tree, 2 * rt + 1, mid + 1, right);
    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}

// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
    if (tree[rt].lazy != 0) {
        tree[rt * 2].data = (tree[rt * 2].data + tree[rt].lazy * (len - len / 2)) % P;
        tree[rt * 2].lazy = (tree[rt * 2].lazy + tree[rt].lazy) % P;
        tree[rt * 2 + 1].data = (tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2)) % P;
        tree[rt * 2 + 1].lazy = (tree[rt * 2 + 1].lazy + tree[rt].lazy) % P;
        tree[rt].lazy = 0;
    }
}

// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
    if (ql > right || qr < left) {
        return 0;
    }
    if (ql <= left && qr >= right) {
        return tree[rt].data;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
    int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
    return (leftsum + rightsum) % P;
}

// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
    if (ul > right || ur < left) return;
    if (ul <= left && ur >= right) {
        tree[rt].data = (tree[rt].data + value * (right - left + 1)) % P;
        tree[rt].lazy = (tree[rt].lazy + value) % P;
        return;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    updateRange(tree, 2 * rt, left, mid, ul, ur, value);
    updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}

// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    sz[u] = 1;
    heavy[u] = 0;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
}

// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
    pos[u] = ++current_pos;
    top[u] = chain_top;
    if (heavy[u]) {
        dfs2(heavy[u], u, chain_top);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            dfs2(v, u, v);
        }
    }
}

// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}

// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        res = (res + query(tree, 1, 1, N, pos[top[y]], pos[y])) % P;
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    res = (res + query(tree, 1, 1, N, pos[x], pos[y])) % P;
    return res;
}

// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    updateRange(tree, 1, 1, N, l, r, z);
}

// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    return query(tree, 1, 1, N, l, r);
}

// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) {
            swap(x, y);
        }
        x = parent[top[x]];
    }
    return depth[x] < depth[y] ? x : y;
}

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

    cin >> N >> M >> R >> P;
    for (int i = 1; i <= N; ++i) {
        cin >> val[i];
    }
    for (int i = 1; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 第一次DFS预处理
    dfs1(R, 0);
    current_pos = 0;
    // 第二次DFS进行重链剖分
    dfs2(R, 0, R);

    // 构建线段树
    vector<int> datas(N + 1);
    for (int i = 1; i <= N; ++i) {
        datas[pos[i]] = val[i] % P;
    }

    tree.resize(4 * (N + 1));
    build(datas, tree, 1, 1, N);

    // 处理操作
    while (M--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {  // 路径更新
            int x, y, z;
            cin >> x >> y >> z;
            pathUpdate(x, y, z);
        } else if (cmd == 2) {  // 路径查询
            int x, y;
            cin >> x >> y;
            cout << pathQuery(x, y) << '\n';
        } else if (cmd == 3) {  // 子树更新
            int x, z;
            cin >> x >> z;
            subtreeUpdate(x, z);
        } else if (cmd == 4) {  // 子树查询
            int x;
            cin >> x;
            cout << subtreeQuery(x) << '\n';
        }
    }

    return 0;
}
树链剖分 shulianpoufen 4.4.2 树链剖分
219 行
CPP JSON
【树链剖分(Heavy-Light Decomposition)——无 MOD 版】 ▪ dfs1(u, p) — 第一次 DFS:计算 parent、depth、sz、heavy(重儿子) ▪ dfs2(u, h) — 第二次 DFS:分配 pos(DFS 序)、top(重链顶部),优先遍历重儿子 ▪ build(datas, tree, rt, l, r) — 线段树建树,O(N) ▪ pushDown(tree, rt, len) — 下传懒标记,O(1) ▪ query(tree, rt, l, r, ql, qr) — 线段树区间查询(无 MOD),O(log N) ▪ updateRange(tree, rt, l, r, ul, ur, val) — 线段树区间更新(无 MOD),O(log N) ▪ queryPath(u, v) / updatePath(u, v, val) — 树上路径查询/更新,O(log² N) 与 ID=27 功能一致但不含模数,适用于不需要取模的树上路径/子树操作。
C++ 219 行 CPP
const int MAXN = 1e5 + 5;  // 最大节点数
int N, M, R;  // 节点数、操作数、根节点
vector<int> adj[MAXN];  // 邻接表存储树结构
int val[MAXN];  // 节点初始权值

// 树链剖分相关变量
int parent[MAXN];  // 父节点
int depth[MAXN];   // 节点深度
int sz[MAXN];      // 子树大小
int heavy[MAXN];   // 重儿子
int pos[MAXN];     // 节点在线段树中的位置
int top[MAXN];     // 所在重链的顶部节点
int current_pos;   // 当前DFS序位置

// 线段树节点结构
struct node {
    int data;  // 节点值
    int lazy;  // 懒标记
    node() : data(0), lazy(0) {}
};

vector<node> tree;  // 线段树

// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
    if (left == right) {
        tree[rt].data = datas[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(datas, tree, 2 * rt, left, mid);
    build(datas, tree, 2 * rt + 1, mid + 1, right);
    tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}

// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
    if (tree[rt].lazy != 0) {
        tree[rt * 2].data = tree[rt * 2].data + tree[rt].lazy * (len - len / 2);
        tree[rt * 2].lazy = tree[rt * 2].lazy + tree[rt].lazy;
        tree[rt * 2 + 1].data = tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2);
        tree[rt * 2 + 1].lazy = tree[rt * 2 + 1].lazy + tree[rt].lazy;
        tree[rt].lazy = 0;
    }
}

// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
    if (ql > right || qr < left) {
        return 0;
    }
    if (ql <= left && qr >= right) {
        return tree[rt].data;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
    int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
    return leftsum + rightsum;
}

// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
    if (ul > right || ur < left) return;
    if (ul <= left && ur >= right) {
        tree[rt].data = tree[rt].data + value * (right - left + 1);
        tree[rt].lazy = tree[rt].lazy + value;
        return;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    updateRange(tree, 2 * rt, left, mid, ul, ur, value);
    updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
    tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}

// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    sz[u] = 1;
    heavy[u] = 0;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
}

// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
    pos[u] = ++current_pos;
    top[u] = chain_top;
    if (heavy[u]) {
        dfs2(heavy[u], u, chain_top);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            dfs2(v, u, v);
        }
    }
}

// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}

// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        res = res + query(tree, 1, 1, N, pos[top[y]], pos[y]);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    res = res + query(tree, 1, 1, N, pos[x], pos[y]);
    return res;
}

// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    updateRange(tree, 1, 1, N, l, r, z);
}

// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    return query(tree, 1, 1, N, l, r);
}

// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) {
            swap(x, y);
        }
        x = parent[top[x]];
    }
    return depth[x] < depth[y] ? x : y;
}

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

    cin >> N >> M >> R;
    for (int i = 1; i <= N; ++i) {
        cin >> val[i];
    }
    for (int i = 1; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 第一次DFS预处理
    dfs1(R, 0);
    current_pos = 0;
    // 第二次DFS进行重链剖分
    dfs2(R, 0, R);

    // 构建线段树
    vector<int> datas(N + 1);
    for (int i = 1; i <= N; ++i) {
        datas[pos[i]] = val[i];
    }

    tree.resize(4 * (N + 1));
    build(datas, tree, 1, 1, N);

    // 处理操作
    while (M--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {  // 路径更新
            int x, y, z;
            cin >> x >> y >> z;
            pathUpdate(x, y, z);
        } else if (cmd == 2) {  // 路径查询
            int x, y;
            cin >> x >> y;
            cout << pathQuery(x, y) << '\n';
        } else if (cmd == 3) {  // 子树更新
            int x, z;
            cin >> x >> z;
            subtreeUpdate(x, z);
        } else if (cmd == 4) {  // 子树查询
            int x;
            cin >> x;
            cout << subtreeQuery(x) << '\n';
        }
    }

    return 0;
}
斯坦纳树 (游览计划) 方格图 4.4.3 树论综合
80 行
CPP JSON
【斯坦纳树 (游览计划)(方格图)】 斯坦纳树(Steiner Tree)模板,连接指定点集的最小树。 核心函数: void in(Re &x) — 核心算法函数 void SPFA(Re s) — SPFA最短路 void dfs(Re i,Re j,Re s) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:Steiner_Tree, PRE, QAQ 关键配置: N=12 说明:freopen("123.txt","r",stdin);
C++ 79 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=12;
int n,m,ct,A[N][N],B[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Steiner_Tree{
	struct PRE{int i,j,s;PRE(Re I=0,Re J=0,Re S=0){i=I,j=J,s=S;}}pre[N][N][1024+3];
	int vis[N][N],dp[N][N][1024+3],wx[4]={-1,0,1,0},wy[4]={0,1,0,-1};
	struct QAQ{int x,y;QAQ(Re X=0,Re Y=0){x=X,y=Y;}};
	queue<QAQ>Q;
	inline void SPFA(Re s){
		while(!Q.empty()){
			QAQ now=Q.front();Q.pop();
			Re x=now.x,y=now.y;vis[x][y]=0;
			for(Re o=0;o<4;++o){
				Re nx=x+wx[o],ny=y+wy[o];
				if(nx<1||nx>n||ny<1||ny>m)continue;
				if(dp[nx][ny][s]>dp[x][y][s]+B[nx][ny]){
					dp[nx][ny][s]=dp[x][y][s]+B[nx][ny],pre[nx][ny][s]=PRE(x,y,s);
					if(!vis[nx][ny])Q.push(QAQ(nx,ny)),vis[nx][ny]=1;
				}
			}
		}
	}
	int Ans[N][N];
	inline void dfs(Re i,Re j,Re s){
		Ans[i][j]=1;PRE to=pre[i][j][s];
		if(to.s){
			dfs(to.i,to.j,to.s);
			if(to.i==i&&to.j==j)dfs(to.i,to.j,s^to.s);
		}
	}
	inline void sakura(){
		memset(dp,63,sizeof(dp));
		Re V=(1<<ct)-1,inf=dp[0][0][0];
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				if(A[i][j])dp[i][j][1<<A[i][j]-1]=0;
		for(Re s=0;s<=V;++s){
			for(Re i=1;i<=n;++i)
				for(Re j=1;j<=m;++j){
					for(Re t=(s-1)&s,tmp;t;t=(t-1)&s)
						if((tmp=dp[i][j][t]+dp[i][j][s^t]-B[i][j])<dp[i][j][s])
							dp[i][j][s]=tmp,pre[i][j][s]=PRE(i,j,t);
					if(dp[i][j][s]!=inf)Q.push(QAQ(i,j)),vis[i][j]=1;
				}
			SPFA(s);
		}
		Re ans=2e9,x,y;
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				if(A[i][j])ans=dp[x=i][y=j][V];
		printf("%d\n",ans);
		dfs(x,y,V);
		for(Re i=1;i<=n;puts(""),++i)
			for(Re j=1;j<=m;++j)
				putchar(A[i][j]?'x':(Ans[i][j]?'o':'_'));
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j){
			in(B[i][j]);
			if(!B[i][j])A[i][j]=++ct;
		}
	T1.sakura();
}
斯坦纳树 普通无向图 4.4.3 树论综合
45 行
CPP JSON
【斯坦纳树(普通无向图)】 斯坦纳树(Steiner Tree)模板,连接指定点集的最小树。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void SPFA(Re s) — SPFA最短路 核心结构体:QAQ 关键配置: N=103,M=503 说明:freopen("123.txt","r",stdin);
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=503;
int n,m,o,x,y,z,K,ans,pan[N],head[N],dp[N][1024+3];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void SPFA(Re s){
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dp[x][s]+a[i].w<dp[to=a[i].to][s]){
				dp[to][s]=dp[x][s]+a[i].w;
				if(!pan[to])Q.push(to),pan[to]=1;
			}
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(K);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	memset(dp,63,sizeof(dp));Re inf=dp[0][0];
	for(Re i=1;i<=K;++i)in(x),dp[x][1<<i-1]=0,ans=x;
	Re V=(1<<K)-1;
	for(Re s=0;s<=V;++s){
		for(Re i=1;i<=n;++i){
			for(Re t=(s-1)&s;t;t=(t-1)&s)
				dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s^t]);
			if(dp[i][s]!=inf)Q.push(i),pan[i]=1;
		}
		SPFA(s);
	}
	printf("%d ",dp[ans][V]);
}
DFS序+分治 Lomsat gelral 4.4.3 树论综合
50 行
CPP JSON
【DFS序+分治(Lomsat gelral)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 void sakura(Re L,Re R) — 后缀数组 核心结构体:QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 49 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,tmp,dfn_O,A[N],Q[N],cnt[N],dfn[N],idx[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
    idx[dfn[x]=++dfn_O]=x,size[x]=1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
    while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
    ++cnt[Q[++t]=A[x]];
    if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
    else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void sakura(Re L,Re R){
    if(L==R){if(size[idx[L]]==1)Ans[idx[L]]=A[idx[L]];return;}
    Re mid=L+R>>1;
    sakura(L,mid),sakura(mid+1,R);
    Re p=mid;CL();
    for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
        insert(idx[i]);
        if(j<=mid)continue;
        while(p<j)insert(idx[++p]);
        Ans[idx[i]]=ans;
    }
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    dfs(1,0),sakura(1,n);
    for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
Dsu on tree Lomsat gelral 4.4.3 树论综合
54 行
CPP JSON
【Dsu on tree(Lomsat gelral)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 void addson(Re x,Re fa) — 加法更新 void sakura(Re x,Re fa) — 后缀数组 核心结构体:QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int o,n,m,x,y,t,K,tmp,A[N],Q[N],cnt[N],son[N],size[N],head[N];LL ans,Ans[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
	size[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x),size[x]+=size[to];
			if(size[to]>size[son[x]])son[x]=to;
		}
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;ans=tmp=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=A[x]];
	if(cnt[A[x]]>tmp)tmp=cnt[ans=A[x]];
	else if(cnt[A[x]]==tmp)ans+=A[x];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
	if(son[x])sakura(son[x],x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
	insert(x),Ans[x]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0),sakura(1,0);
	for(Re i=1;i<=n;++i)printf("%lld ",Ans[i]);
}
Prufer序列 get_prufer 4.4.3 树论综合
39 行
CPP JSON
【Prufer序列】 Prufer 序列模板,n 个节点的有标号无根树计数。 核心函数: void in(Re &x) — 核心算法函数 LL get_prufer(无参数) — 获取值 LL get_fa(无参数) — 获取值 关键配置: N=5e6+3 说明:printf("Prufer: ");for(Re i=1;i<=n-2;++i)printf("%d ",pf[i]);puts("");;printf("fa: ");for(Re i=1;i<=n-1;++i)printf("%d ",fa[i]);puts("");;freopen("123.txt","r",stdin);
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e6+3;
int n,op,fa[N],pf[N],son[N];LL ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL get_prufer(){
	for(Re i=1;i<=n-1;++i)in(fa[i]),++son[fa[i]];
	for(Re i=1,j=1;i<=n-2;++i,++j){
		while(son[j])++j;pf[i]=fa[j];
		while(i<=n-2&&!--son[pf[i]]&&pf[i]<j)pf[i+1]=fa[pf[i]],++i;
	}
//	printf("Prufer: ");for(Re i=1;i<=n-2;++i)printf("%d ",pf[i]);puts("");
	for(Re i=1;i<=n-2;++i)ans^=(LL)i*pf[i];
	return ans;
}
inline LL get_fa(){
	for(Re i=1;i<=n-2;++i)in(pf[i]),++son[pf[i]];pf[n-1]=n;
	for(Re i=1,j=1;i<=n-1;++i,++j){
		while(son[j])++j;fa[j]=pf[i];
		while(i<=n-1&&!--son[pf[i]]&&pf[i]<j)fa[pf[i]]=pf[i+1],++i;
	}
//	printf("fa: ");for(Re i=1;i<=n-1;++i)printf("%d ",fa[i]);puts("");
	for(Re i=1;i<=n-1;++i)ans^=(LL)i*fa[i];
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(op),printf("%lld\n",op<2?get_prufer():get_fa());
}
基环树 Island 求基环树森林直径之和 4.4.3 树论综合
60 行
CPP JSON
【基环树(Island 求基环树森林直径之和)】 基环树(Pseudo Tree)模板,含一个环的 n 节点 n 边连通图。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 LL max(LL a,LL b) — 核心算法函数 int find_circle(Re x,Re p) — 查找(并查集寻根/二分查找) void Tree_dp(Re x) — 核心算法函数 LL pp(Re j) — 核心算法函数 LL sakura(Re root) — 后缀数组 核心结构体:QAQ 关键配置: N=1e6+3
C++ 60 行 CPP
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#define Re register int
const int N=1e6+3;
#define LL long long
int n,m,x,y,o=1,h,t,st,cnt,In[N],cir[N],pan[N],head[N];LL ans,tmp,Q[N<<1],S[N<<1],dp[N<<1],dis[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline LL max(LL a,LL b){return a>b?a:b;}
inline int find_circle(Re x,Re p){
	if(In[x]){st=x,cir[++cnt]=x,pan[x]=1;return 1;}
	In[x]=1;
	for(Re i=head[x];i;i=a[i].next)
		if(i!=(p^1)&&find_circle(a[i].to,i)){
			pan[x]=1;
			if(x==st){S[0]=S[1]-a[i].w;return 0;}
			cir[++cnt]=x,S[cnt]=S[cnt-1]+a[i].w;
			return 1;
		}
	return 0;
}
inline void Tree_dp(Re x){
	pan[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan[to=a[i].to]){
			Tree_dp(to);
			tmp=max(tmp,dis[x]+a[i].w+dis[to]);
			dis[x]=max(dis[x],dis[to]+a[i].w);
		}
}
inline LL pp(Re j){return dp[j]-S[j];}
inline LL sakura(Re root){
	S[0]=cnt=st=0;find_circle(root,0);
	LL ans1=0,ans2=0;tmp=0;
	for(Re i=1;i<=cnt;++i){
		tmp=0,Tree_dp(cir[i]),ans1=max(ans1,tmp);
		dp[i+cnt]=dp[i]=dis[cir[i]];
		S[i+cnt]=S[i+cnt-1]+S[i]-S[i-1];
	}
	h=1,t=0,Q[++t]=1;//ans=max(dp[i]+dp[j]+S[i]-S[j]) i-j+1<=cnt i-cnt+1<=j<i
	for(Re i=2;i<=(cnt<<1);++i){
		while(h<=t&&Q[h]<i-cnt+1)++h;
		if(h<=t)ans2=max(ans2,dp[i]+S[i]+pp(Q[h]));
		while(h<=t&&pp(Q[t])<=pp(i))--t;
		Q[++t]=i;
	}
	return max(ans1,ans2);
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(x),in(y),add(i,x,y),add(x,i,y);
	for(Re i=1;i<=n;++i)if(!pan[i])ans+=sakura(i);
	printf("%lld",ans);
}
最近公共祖先LCA LCT 4.4.3 树论综合
75 行
CPP JSON
【最近公共祖先LCA(LCT)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=5e5+3 说明:freopen("123.txt","r",stdin);
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,tag,ps[2];}tr[N];
	inline void pushup(Re p){}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline int access(Re p){
		Re son=0;
		for(;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
		return son;
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x),tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int lca(Re x,Re y){access(x);return access(y);}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(root),m=n-1;
	while(m--)in(x),in(y),LCT.link(x,y);LCT.makeroot(root);
	while(T--)in(x),in(y),printf("%d\n",LCT.lca(x,y));
}
最近公共祖先LCA RMQ 4.4.3 树论综合
46 行
CPP JSON
【最近公共祖先LCA(RMQ)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void build(Re rt) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 核心结构体:QAQ, LCA 关键配置: N=5e5+3,logN=20 说明:freopen("123.txt","r",stdin);
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,logN=20;
int n,m,o,x,y,T,rt,head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int O,lg[N<<1],Qx[N<<1],Qd[N<<1],fir[N],deep[N],f[N<<1][23],ans[N<<1][23];
	inline void dfs(Re x,Re fa){
		Qx[fir[x]=++O]=x,Qd[O]=deep[x]=deep[fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dfs(to,x),Qx[++O]=x,Qd[O]=deep[x];
	}
	inline void build(Re rt){
		dfs(rt,0),lg[0]=-1;
		for(Re i=1;i<=O;++i)f[i][0]=Qd[i],ans[i][0]=Qx[i],lg[i]=lg[i>>1]+1;
		for(Re j=1;j<=logN;++j)
			for(Re i=1;i+(1<<j)-1<=O;++i)
				if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
				else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
	}
	inline int lca(Re x,Re y){
		Re L=fir[x],R=fir[y];
		if(L>R)swap(L,R);
		Re m=lg[R-L+1];
		return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(rt),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(rt);
	while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
最近公共祖先LCA 倍增 4.4.3 树论综合
37 行
CPP JSON
【最近公共祖先LCA(倍增)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void add(Re x,Re y) — 加法更新 核心结构体:QAQ, LCA 关键配置: N=5e5+3,M=5e5+3,logN=19
C++ 36 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19;
int T,Q,n,m,x,y,o,root,head[N];
struct QAQ{int to,next;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int deep[N],ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
		if(x==y)return x;
		for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T1;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
int main(){
	in(n),in(Q),in(root),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs(root,0);
	while(Q--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
最近公共祖先LCA 树剖 4.4.3 树论综合
51 行
CPP JSON
【最近公共祖先LCA(树剖)】 最近公共祖先(LCA)模板(倍增法/树剖/Tarjan)。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void kill(Re rt) — 核心算法函数 int lca(Re x,Re y) — 查询最近公共祖先 核心结构体:Killed_Tree, QAQ 关键配置: N=5e5+3 说明:freopen("123.txt","r",stdin);
C++ 50 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5e5+3;
int n,m,x,y,T,root;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Killed_Tree{
	struct QAQ{int to,next;}a[N<<1];
	int o,head[N];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	int id_o,id[N],fa[N],son[N],top[N],deep[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x);
				size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		id[x]=++id_o,top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),in(root),m=n-1;
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.kill(root);
	while(T--)in(x),in(y),printf("%d\n",T1.lca(x,y));
}
树的直径 dfs 4.4.3 树论综合
35 行
CPP JSON
【树的直径(dfs)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DFS 关键配置: N=1e4+3,M=3e5+3
C++ 34 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DFS{
	int cur,dis[N];
	inline void dfs(Re x,Re fa){
		if(dis[x]>dis[cur])cur=x;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dis[to]=dis[x]+a[i].w,dfs(to,x);
	}
	inline int sakura(){
		dfs(1,0);
		memset(dis,0,sizeof(dis));
		dfs(cur,0);
		return dis[cur];
	}
}T1;
int main(){
	in(n),m=n-1;
    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
    printf("%d\n",T1.sakura());
}
树的直径 dp 4.4.3 树论综合
47 行
CPP JSON
【树的直径(dp)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 void dfs(Re x,Re fa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DP1, Tree_Diam_DP2 关键配置: N=1e4+3,M=3e5+3 说明:printf("%d\n",T2.sakura());
C++ 46 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e4+3,M=3e5+3;
int n,m,x,y,o,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DP1{
	int ans,dis[N];
	inline void dfs(Re x,Re fa){
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x);
				ans=max(ans,dis[x]+dis[to]+a[i].w);
				dis[x]=max(dis[x],dis[to]+a[i].w);
			}
	}
	inline int sakura(){dfs(1,0);return ans;}
}T1;
struct Tree_Diam_DP2{
	int ans,dis[N][2];
	inline void dfs(Re x,Re fa){
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x);
				if(dis[x][0]<(tmp=dis[to][0]+a[i].w))dis[x][1]=dis[x][0],dis[x][0]=tmp;
				else dis[x][1]=max(dis[x][1],tmp);
			}
		ans=max(ans,dis[x][1]+dis[x][0]);
	}
	inline int sakura(){dfs(1,0);return ans;}
}T2;
int main(){
	in(n),m=n-1;
    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
    printf("%d\n",T1.sakura());
//    printf("%d\n",T2.sakura());
}
树的重心 add 4.4.3 树论综合
42 行
CPP JSON
【树的重心】 树的重心算法模板(DFS 统计子树大小)。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:QAQ, Tree_Diam_DP1 关键配置: N=2e4+3,inf=2e9
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2e4+3,inf=2e9;
int n,m,x,y,o,T,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct Tree_Diam_DP1{
	int ans,dp[N],size[N];
	inline void dfs(Re x,Re fa){
		size[x]=1,dp[x]=0;
		for(Re i=head[x],to,tmp;i;i=a[i].next)
			if((to=a[i].to)!=fa){
				dfs(to,x),size[x]+=size[to];
				dp[x]=max(dp[x],size[to]);
			}
		if(n-size[x])dp[x]=max(dp[x],n-size[x]);
	}
	inline void sakura(){
		dfs(1,0),dp[ans=0]=inf;
		for(Re i=1;i<=n;++i)if(dp[i]<dp[ans])ans=i;
	}
}T1;
int main(){
	in(T);
	while(T--){
		memset(head,0,sizeof(head));
		in(n),m=n-1,o=0;
	    while(m--)in(x),in(y),add(x,y,1),add(y,x,1);
	    T1.sakura();
		printf("%d %d\n",T1.ans,T1.dp[T1.ans]);
	}
}
虚树 Kingdom and its Cities 4.4.3 树论综合
79 行
CPP JSON
【虚树(Kingdom and its Cities)】 虚树(Virtual Tree)模板,只保留关键点的压缩树。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 bool cmp(Re x,Re y) — 核心算法函数 void add(Re x,Re y) — 加法更新 void insert(Re x) — 插入元素 void dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ, LCA, Virtual_Tree, QAQ 关键配置: N=1e5+3,logN=17 说明:freopen("123.txt","r",stdin);
C++ 78 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=17;
int n,m,x,y,o,T,dfn_o,dfn[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][20];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1,dfn[x]=++dfn_o;
		for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re j=logN;j>=0;--j)if(deep[ant[x][j]]>=deep[y])x=ant[x][j];
		if(x==y)return x;
		for(Re j=logN;j>=0;--j)if(ant[x][j]!=ant[y][j])x=ant[x][j],y=ant[y][j];
		return ant[x][0];
	}
}T1;
inline bool cmp(Re x,Re y){return dfn[x]<dfn[y];}
struct Virtual_Tree{
	int t,o,ans,A[N],Q[N],key[N],head[N];
	struct QAQ{int to,next;}a[N<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void insert(Re x){// 撤销操作
		Re lca=T1.lca(Q[t],x);
		while(t>1&&deep[Q[t-1]]>deep[lca])add(Q[t-1],Q[t]),--t;
		if(t&&deep[Q[t]]>deep[lca])add(lca,Q[t--]);
		if(!t||Q[t]!=lca)Q[++t]=lca;
		Q[++t]=x;
	}
	inline void dfs(Re x){// 撤销操作
		if(key[x])
			for(Re i=head[x],to;i;i=a[i].next){
				dfs(to=a[i].to);
				if(key[to])key[to]=0,++ans;
			}
		else{
			for(Re i=head[x],to;i;i=a[i].next)
				dfs(to=a[i].to),key[x]+=key[to],key[to]=0;
			if(key[x]>1)key[x]=0,++ans;
		}
		head[x]=0;
	}
	inline void sakura(){
		in(m);Re flag=1;ans=o=t=0;
		for(Re i=1;i<=m;++i)in(A[i]),key[A[i]]=1;
		for(Re i=1;i<=m&&flag;++i)flag&=(!key[T1.ant[A[i]][0]]);
		if(!flag){
			for(Re i=1;i<=m;++i)key[A[i]]=0;
			puts("-1");return;
		}
		sort(A+1,A+m+1,cmp),Q[++t]=1;
		for(Re i=1+(A[1]==1);i<=m;++i)insert(A[i]);
		while(t>1)add(Q[t-1],Q[t]),--t;
		dfs(1),key[1]=0;
		printf("%d\n",ans);
	}
}T2;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs(1,0),in(T);
	while(T--)T2.sakura();
}
天天爱跑步 mid 4.4.3 树论综合
77 行
CPP JSON
【天天爱跑步】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int merge(Re p,Re q) — 合并操作 int ask(Re p,Re L,Re R,Re x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QWQ, Segmemt_Tree, QAQ, LCA 关键配置: N=3e5+3,logN=19
C++ 76 行 CPP
#include<algorithm>
#include<cstdio>
#define pl tr[p].lp 
#define pr tr[p].rp
#define mid (L+R>>1)
#define Re register int
const int N=3e5+3,logN=19;
int x,y,n,m,T,o,lca,w[N],pt[N],ans[N],head[N],deep[N];
struct QWQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
struct Segmemt_Tree{
	struct QAQ{int g,lp,rp;}tr[N*36];int cnt;
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++cnt;
		if(L==R){tr[p].g+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
	    else change(pr,mid+1,R,x,v);
	}
	inline int merge(Re p,Re q){
	    if(!p)return q;if(!q)return p;
	    tr[p].g+=tr[q].g;
	    pl=merge(pl,tr[q].lp);
		pr=merge(pr,tr[q].rp);
	    return p;
	}
	inline int ask(Re p,Re L,Re R,Re x){
	    if(!p)return 0;
	    if(L==R)return tr[p].g;
	    if(x<=mid)return ask(pl,L,mid,x);
	    else return ask(pr,mid+1,R,x);
	}
}T1;
struct LCA{
	int ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[fa]+1,ant[x][0]=fa;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]>deep[y])std::swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
		if(x==y)return y;
		for(Re i=logN;i>=0;--i)
			if(ant[x][i]==ant[y][i])continue;
			else x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T2;
inline void dfs(Re x,Re fa){
    for(Re i=head[x],to;i;i=a[i].next)
    	if((to=a[i].to)!=fa)
        	dfs(to,x),pt[x]=T1.merge(pt[x],pt[to]);
	ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]-w[x]);
    if(w[x]&&deep[x]+w[x]<=n)ans[x]+=T1.ask(pt[x],1,n<<1,n+deep[x]+w[x]);
}
int main(){
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	for(Re i=1;i<=n;++i)in(w[i]);
	T2.dfs(1,0);
	while(T--){
		in(x),in(y),lca=T2.lca(x,y);
		T1.change(pt[x],1,n<<1,n+deep[x],1);
        T1.change(pt[y],1,n<<1,n+deep[lca]*2-deep[x],1);
        T1.change(pt[lca],1,n<<1,n+deep[x],-1);
        T1.change(pt[T2.ant[lca][0]],1,n<<1,n+deep[lca]*2-deep[x],-1);
	}
	dfs(1,0);
	for(Re i=1;i<=n;++i)printf("%d ",ans[i]);
}
树的直径升级版 每个点可到的最远距离computer HDU 4.4.3 树论综合
46 行
CPP JSON
【树的直径升级版 每个点可到的最远距离computer(HDU)】 树的直径算法模板(两次 BFS/DFS 或树形 DP)。 核心函数: void add(int x,int y,int w) — 加法更新 void dfs(int x,int pa) — 深度优先搜索遍历 void dfsf(int x,int pa) — 深度优先搜索遍历 int sakura(无参数) — 后缀数组 核心结构体:QAQ 说明:����ȹ�������ӵ�ͷ��һ���·����ô�ö��ӵķ�������������λ���׵Ĵδ���������ȡ���;����·û������ͷ����ô���ķ�������Ǹ��׵������������ȡ���
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int n,b,c,d,t,longson[10005],d1[10005],d2[10005],df[10005],head[10005];
struct QAQ{int to,next,w;}a[20005];
inline void add(int x,int y,int w){a[++t].to=y,a[t].w=w,a[t].next=head[x],head[x]=t;}
inline void dfs(int x,int pa){
	for(R i=head[x];i;i=a[i].next){
		R s,to=a[i].to;
		if(to==pa)continue;
		dfs(to,x);s=d1[to]+a[i].w;
		if(s>d1[x])d2[x]=d1[x],d1[x]=s,longson[x]=to;
		else d2[x]=max(d2[x],s);
	}
}
inline void dfsf(int x,int pa){
	for(R i=head[x];i;i=a[i].next){
		R to=a[i].to;
		if(to==pa)continue;
		if(longson[x]==to)df[to]=a[i].w+max(d2[x],df[x]);
		else df[to]=a[i].w+max(d1[x],df[x]);
		dfsf(to,x);
	}
}
inline int sakura(){
	while(~scanf("%d",&n)){
		memset(longson,0,sizeof(longson));
		memset(head,0,sizeof(head));
		memset(d1,0,sizeof(d1));
		memset(d2,0,sizeof(d2));
		memset(df,0,sizeof(df));
		memset(a,0,sizeof(a));t=0;
		for(R i=2;i<=n;i++){
			scanf("%d%d",&b,&c);
			add(i,b,c),add(b,i,c);
		}
		dfs(1,0);dfsf(1,0);
		for(R i=1;i<=n;i++)printf("%d\n",max(d1[i],df[i]));
	}
	return 0;
}
int QAQWQ=sakura();
int main(){}
雪松果树 DFS序+分治 4.4.3 树论综合
76 行
CPP JSON
【雪松果树(DFS序+分治)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void add(Re x,Re y,Re id) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int kant(Re x,Re k) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 核心结构体:QAQ, Query, QAQ, LCA 关键配置: N=1e6+5,logN=14 说明:freopen("123.txt","r",stdin);
C++ 75 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,dfn_O,A[N],Q[N],dfn[N],idx[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
	int o,head[N];
	struct QAQ{int to,id,next;}a[N];
	inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][15];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int kant(Re x,Re k){
		for(Re i=logN;i>=0;--i)
			if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
		return x;
	}
}T1;
inline void dfs(Re x,Re fa){
	idx[dfn[x]=++dfn_O]=x,size[x]=1,deep[x]=deep[fa]+1;
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x),size[x]+=size[to];
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void getans(Re x){
	for(Re i=QT.head[x];i;i=QT.a[i].next)
		Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
inline void sakura(Re L,Re R){
    if(L==R){if(size[idx[L]]==1)CL(),insert(idx[L]),getans(idx[L]);return;}
    Re mid=L+R>>1;
    sakura(L,mid),sakura(mid+1,R);
    Re p=mid;CL();
    for(Re i=mid,j;i>=L&&(j=i+size[idx[i]]-1)<=R;--i){
        insert(idx[i]);
        if(j<=mid)continue;
        while(p<j)insert(idx[++p]);
        getans(idx[i]);
    }
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=2;i<=n;++i)in(x),add(x,i);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
	dfs(1,0),sakura(1,n);
	for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
雪松果树 Dsu on tree 4.4.3 树论综合
73 行
CPP JSON
【雪松果树(Dsu on tree)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void add(Re x,Re y,Re id) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int kant(Re x,Re k) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 void CL(无参数) — 核心算法函数 void insert(Re x) — 插入元素 核心结构体:QAQ, Query, QAQ, LCA 关键配置: N=1e6+5,logN=14 说明:freopen("123.txt","r",stdin);
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+5,logN=14;
int o,n,m,x,y,t,T,A[N],Q[N],Ans[N],cnt[N],son[N],deep[N],size[N],head[N];
struct QAQ{int to,next;}a[N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
struct Query{
	int o,head[N];
	struct QAQ{int to,id,next;}a[N];
	inline void add(Re x,Re y,Re id){a[++o].to=y,a[o].id=id,a[o].next=head[x],head[x]=o;}
}QT;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int ant[N][15];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
	}
	inline int kant(Re x,Re k){
		for(Re i=logN;i>=0;--i)
			if((1<<i)<=k)k-=(1<<i),x=ant[x][i];
		return x;
	}
}T1;
inline void dfs(Re x,Re fa){
	size[x]=1,deep[x]=deep[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x),size[x]+=size[to];
			if(size[to]>size[son[x]])son[x]=to;
		}
}
inline void CL(){
	while(t)cnt[Q[t--]]=0;
}
inline void insert(Re x){
	++cnt[Q[++t]=deep[x]];
}
inline void addson(Re x,Re fa){
	insert(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)addson(to,x);
}
inline void sakura(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])sakura(to,x),CL();
	if(son[x])sakura(son[x],x);
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x])addson(to,x);
	insert(x);
	for(Re i=QT.head[x];i;i=QT.a[i].next)
		Ans[QT.a[i].id]=cnt[deep[x]+QT.a[i].to];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=2;i<=n;++i)in(x),add(x,i);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i)in(x),in(y),QT.add(T1.kant(x,y),y,i);
	dfs(1,0),sakura(1,n);
	for(Re i=1;i<=T;++i)printf("%d ",max(Ans[i]-1,0));
}
Qtree7 LCT维护同色连通块最大点权 4.4.3 树论综合
87 行
CPP JSON
【Qtree7(LCT维护同色连通块最大点权)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 void erase(Re x) — 删除元素 int top(无参数) — 获取栈顶/堆顶元素 void pushup(Re p) — 上推更新节点信息 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 核心结构体:QAQ, Queue, Link_Cut_Tree, QAQ 关键配置: N=1e5+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 86 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,x,y,o,T,op,A[N],co[N],fa[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Queue{
	priority_queue<int>Q,D;
	inline void insert(Re x){Q.push(x);}
	inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
	inline int top(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty()?-inf:Q.top();
	}
};
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	struct QAQ{int fa,max,ps[2];}tr[N];Queue si[N];
	inline void pushup(Re p){
		tr[p].max=max(max(A[p],si[p].top()),max(tr[pl].max,tr[pr].max));
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),si[p].insert(tr[pr].max),pr=son,si[p].erase(tr[pr].max),pushup(p);
	}
	inline void link(Re p,Re fa){
		access(p),splay(p),access(fa),splay(fa),si[pf=fa].insert(tr[p].max),pushup(fa);
	}
	inline void cut(Re p,Re fa){
		access(p),splay(p),splay(fa),pf=tr[fa].ps[1]=0,pushup(fa);
	}
	inline int ask(Re p){
		access(p),splay(p);while(pl)p=pl;splay(p);return tr[pr].max;
	}
	inline void change(Re p,Re v){
		access(p),splay(p),A[p]=v,pushup(p);
	}
}LCT[2];
inline void dfs(Re x,Re Fa){
	LCT[0].tr[x].max=LCT[1].tr[x].max=A[x];
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=Fa)dfs(to,x);
	LCT[co[x]].link(x,fa[x]=Fa);
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),m=n-1,LCT[0].tr[0].max=LCT[1].tr[0].max=-inf;
    while(m--)in(x),in(y),add(x,y),add(y,x);
    for(Re i=1;i<=n;++i)in(co[i]);
    for(Re i=1;i<=n;++i)in(A[i]);
    in(T),dfs(1,n+1);
    while(T--){
    	in(op),in(x);
    	if(op<1)printf("%d\n",LCT[co[x]].ask(x));
    	else if(op<2)LCT[co[x]].cut(x,fa[x]),LCT[co[x]^=1].link(x,fa[x]);
    	else in(y),LCT[co[x]].change(x,y);
	}
}
[RCOI] XOR (LCT 计算原树信息) TLE 30pt 4.4.3 树论综合
96 行
CPP JSON
【[RCOI] XOR (LCT 计算原树信息)(TLE 30pt)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e6+3,M=2e6+3
C++ 95 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e6+3,M=2e6+3;
int n,m,x,y,T,op,HYJ,Ans,root,A[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,si,ans,tag,shi,yuan,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].shi=A[p]^tr[pl].shi^tr[pr].shi;
		tr[p].ans=A[p]^tr[p].si^tr[pl].ans^tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline int access(Re p){
		Re son=0;
		for(;p;son=p,p=pf)
			splay(p),tr[p].si^=tr[pr].ans,tr[p].si^=tr[pr=son].ans,pushup(p);
		return son;
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){
		makeroot(x);
		if(findroot(y)!=x)tr[tr[x].fa=y].si^=tr[x].ans,pushup(y);
	}
	inline int lca(Re x,Re y){access(x);return access(y);}
	
	inline int ask_son(Re p){access(p);return tr[pr].ans^tr[p].si^A[p];}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(HYJ),in(T),m=n-1,T+=HYJ,root=1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),LCT.link(x,y);
	LCT.makeroot(root);
//	Ans=0;for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
//	printf("%d\n",Ans);return 0;
	while(T--){
		in(op),in(x);
//		if(op<2)LCT.makeroot(root=x),printf("%d\n",Ans);
		if(op<2){
			LCT.makeroot(root=x);Ans=0;
			for(Re i=1;i<=n;++i)Ans^=LCT.ask_son(i);
			printf("%d\n",Ans);
		}
		else if(op<3)in(y),LCT.access(x),LCT.splay(x),A[x]=y,LCT.pushup(x);
		else if(op<4)in(y),printf("%d\n",LCT.lca(x,y));
		else if(op<5)in(y),LCT.split(x,y),printf("%d\n",LCT.tr[y].shi),LCT.makeroot(root);
		else printf("%d\n",LCT.ask_son(x));
		LCT.makeroot(root);
	}
}
LCT 动态树 pushup 4.4.3 树论综合
80 行
CPP JSON
【LCT 动态树】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 79 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T,op,a[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,ans,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].ans=a[p]^tr[pl].ans^tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	for(Re i=1;i<=n;++i)in(a[i]);
	while(T--){
		in(op),in(x),in(y);
		if(!op)LCT.split(x,y),printf("%d\n",LCT.tr[y].ans);
		else if(op<2)LCT.link(x,y);
		else if(op<3)LCT.cut(x,y);
		else LCT.splay(x),a[x]=y,LCT.pushup(x);
	}
}
动态DP (带修树上最大点权独立集) LCT 4.4.3 树论综合
84 行
CPP JSON
【动态DP (带修树上最大点权独立集)(LCT)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) void splay(Re p) — 伸展操作(Splay树) 核心结构体:QAQ, Matrix, Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 83 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
	inline Mat operator*(const Mat &O)const{
		Mat A;
		for(Re i=1;i<=2;++i)
			for(Re j=1;j<=2;++j)
				for(Re k=1;k<=2;++k)
					A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
		return A;
	}
}G[N];
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	struct QAQ{int fa,ps[2];}tr[N];Mat TR[N];
	inline void pushup(Re p){
		TR[p]=G[p];
		if(pl)TR[p]=TR[pl]*TR[p];
		if(pr)TR[p]=TR[p]*TR[pr];
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf){
			splay(p);
			if(pr)G[p].a[1][1]+=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]+=TR[pr].a[1][1];
			pr=son;
			if(pr)G[p].a[1][1]-=max(TR[pr].a[1][1],TR[pr].a[2][1]),G[p].a[1][2]=G[p].a[1][1],G[p].a[2][1]-=TR[pr].a[1][1];
			pushup(p);
		}
	}
	inline void change(Re x,Re v){access(x),splay(x),G[x].a[2][1]+=v-A[x],A[x]=v,pushup(x);}//�޸�x�ĵ�Ȩ(G[x][1])
	inline LL ask(){splay(1);return max(TR[1].a[1][1],TR[1].a[2][1]);}
}T1;
LL g[N][2];
inline void dfs(Re x,Re fa){
	g[x][1]=A[x],T1.tr[x].fa=fa;
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
		dfs(to,x),g[x][0]+=max(g[to][0],g[to][1]),g[x][1]+=g[to][0];
	G[x].a[1][1]=G[x].a[1][2]=g[x][0];
	G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
	T1.pushup(x);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs(1,0);
	while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
动态DP (带修树上最大点权独立集) 树剖 4.4.3 树论综合
99 行
CPP JSON
【动态DP (带修树上最大点权独立集)(树剖)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re x,Mat &v) — 核心算法函数 Mat ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 核心结构体:QAQ, Matrix, killed_Tree, Segment_Tree 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 98 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Mat Matrix
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,o,x,y,T,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[3][3];Mat(){a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;}
	inline Mat operator*(const Mat &O)const{
		Mat A;
		for(Re i=1;i<=2;++i)
			for(Re j=1;j<=2;++j)
				for(Re k=1;k<=2;++k)
					A.a[i][j]=max(A.a[i][j],a[i][k]+O.a[k][j]);
		return A;
	}
}G[N];
int idx[N];
struct killed_Tree{
	struct Segment_Tree{
		#define pl (p<<1)
		#define pr (p<<1|1)
		#define mid ((L+R)>>1)
		Mat tr[N<<2];
		inline void pushup(Re p){tr[p]=tr[pl]*tr[pr];}
		inline void build(Re p,Re L,Re R){
			if(L==R){tr[p]=G[idx[L]];return;}
			build(pl,L,mid),build(pr,mid+1,R);
			pushup(p);
		}
		inline void change(Re p,Re L,Re R,Re x,Mat &v){
			if(L==R){tr[p]=v;return;}
			if(x<=mid)change(pl,L,mid,x,v);
			else change(pr,mid+1,R,x,v);
			pushup(p);
		}
		inline Mat ask(Re p,Re L,Re R,Re l,Re r){
			if(l<=L&&R<=r)return tr[p];
			if(r<=mid)return ask(pl,L,mid,l,r);
			else if(l>mid)return ask(pr,mid+1,R,l,r);
			else return ask(pl,L,mid,l,r)*ask(pr,mid+1,R,l,r);
		}
	}TR;
	int id_O,fa[N],st[N],ed[N],son[N],top[N],deep[N],size[N];LL f[N][2],g[N][2];
	inline void dfs1(Re x,Re Fa){
		deep[x]=deep[fa[x]=Fa]+1,size[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		idx[st[x]=++id_O]=x,ed[rt]=max(ed[rt],id_O),top[x]=rt;
		f[x][0]=g[x][0]=0,f[x][1]=g[x][1]=A[x];
		if(son[x])dfs2(son[x],rt),f[x][0]+=max(f[son[x]][0],f[son[x]][1]),f[x][1]+=f[son[x]][0];
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x]){
				dfs2(to,to);
				f[x][0]+=max(f[to][0],f[to][1]),f[x][1]+=f[to][0];
				g[x][0]+=max(f[to][0],f[to][1]),g[x][1]+=f[to][0];
			}
		G[x].a[1][1]=G[x].a[1][2]=g[x][0];
		G[x].a[2][1]=g[x][1],G[x].a[2][2]=-inf;
	}
	inline LL ask(){Mat F=TR.ask(1,1,n,st[1],ed[1]);return max(F.a[1][1],F.a[2][1]);}
	inline void change(Re x,Re v){//�޸�x�ĵ�Ȩ
		G[x].a[2][1]+=v-A[x],A[x]=v;//�޸�G[x][1]
		while(x){
			Mat F1=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
			TR.change(1,1,n,st[x],G[x]);
			Mat F2=TR.ask(1,1,n,st[top[x]],ed[top[x]]);
			x=fa[top[x]];
			G[x].a[1][1]+=max(F2.a[1][1],F2.a[2][1])-max(F1.a[1][1],F1.a[2][1]),G[x].a[1][2]=G[x].a[1][1];
			G[x].a[2][1]+=F2.a[1][1]-F1.a[1][1];
		}
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs1(1,0),T1.dfs2(1,1),T1.TR.build(1,1,n);
	while(T--)in(x),in(y),T1.change(x,y),printf("%lld\n",T1.ask());
}
大融合 LCT 计算虚子树信息 4.4.3 树论综合
81 行
CPP JSON
【大融合(LCT 计算虚子树信息)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 80 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+3;
int n,x,y,T;char op;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,si,ans,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].ans=1+tr[p].si+tr[pl].ans+tr[pr].ans;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),tr[p].si+=tr[pr].ans,tr[p].si-=tr[pr=son].ans,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){
		makeroot(x);
		if(findroot(y)!=x)tr[tr[x].fa=y].si+=tr[x].ans,pushup(y);
	}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int ask(Re x,Re y){split(x,y);return (tr[x].si+1)*(tr[y].si+1);}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T);
	while(T--){
		scanf(" %c",&op),in(x),in(y);
		if(op=='A')LCT.link(x,y);
		if(op=='Q')printf("%d\n",LCT.ask(x,y));
	}
}
树链剖分 重链剖分 4.4.3 树论综合
110 行
CPP JSON
【树链剖分(重链剖分)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void pushdown(Re p) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re l,Re r,Re v) — 核心算法函数 int ask(Re p,Re l,Re r) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 核心结构体:Killed_Tree, QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3
C++ 109 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,y,z,T,P,op,root,A[N],AA[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Killed_Tree{
	struct QAQ{int to,next;}a[N<<1];
	int o,id_o,fa[N],id[N],idx[N],top[N],son[N],size[N],deep[N],head[N];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	struct Segment_Tree{
		#define pl (p<<1)
		#define pr (p<<1|1)
		#define mid (L+R>>1)
		struct QAQ{int S,l,r,add;}tr[N<<2];
		inline void pushdown(Re p){
			Re v=tr[p].add;
			if(v){
				(tr[pl].S+=v*(tr[pl].r-tr[pl].l+1)%P)%=P,(tr[pl].add+=v)%=P;
				(tr[pr].S+=v*(tr[pr].r-tr[pr].l+1)%P)%=P,(tr[pr].add+=v)%=P;
				tr[p].add=0;
			}
		}
		inline void build(Re p,Re L,Re R){
			tr[p].l=L,tr[p].r=R;
			if(L==R){tr[p].S=AA[L]%P;return;}
			build(pl,L,mid),build(pr,mid+1,R);
			tr[p].S=(tr[pl].S+tr[pr].S)%P;
		}
		inline void change(Re p,Re l,Re r,Re v){
			Re L=tr[p].l,R=tr[p].r;
			if(l<=L&&R<=r){(tr[p].S+=v*(R-L+1)%P)%=P,(tr[p].add+=v)%=P;return;}
			pushdown(p);
			if(l<=mid)change(pl,l,r,v);
			if(r>mid)change(pr,l,r,v);
			tr[p].S=(tr[pl].S+tr[pr].S)%P;
		}
		inline int ask(Re p,Re l,Re r){
			Re L=tr[p].l,R=tr[p].r;
			if(l<=L&&R<=r)return tr[p].S;
			Re ans=0;pushdown(p);
			if(l<=mid)(ans+=ask(pl,l,r))%=P;
			if(r>mid)(ans+=ask(pr,l,r))%=P;
			return ans;
		}
	}TR;
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x);
				size[x]+=size[to];
				if(size[to]>size[son[x]])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		id[x]=++id_o,idx[id_o]=x,AA[id_o]=A[x],top[x]=rt;
		if(!son[x])return;//Ҷ�ڵ�
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void kill(Re rt){dfs1(rt,0),dfs2(rt,rt),TR.build(1,1,n);}
	inline int ask_dis(Re x,Re y){
		Re ans=0;
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			(ans+=TR.ask(1,id[top[x]],id[x]))%=P;
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		(ans+=TR.ask(1,id[x],id[y]))%=P;
		return ans;
	}
	inline void change_dis(Re x,Re y,Re v){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			TR.change(1,id[top[x]],id[x],v);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		TR.change(1,id[x],id[y],v);
	}
	inline int ask_son(Re x){
		return TR.ask(1,id[x],id[x]+size[x]-1);
	}
	inline void change_son(Re x,Re v){
		TR.change(1,id[x],id[x]+size[x]-1,v);
	}
}T1;
int main(){
	in(n),in(T),in(root),in(P),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.kill(root);
	while(T--){
		in(op);
		if(op<2)in(x),in(y),in(z),T1.change_dis(x,y,z%P);
		else if(op<3)in(x),in(y),printf("%d\n",T1.ask_dis(x,y));
		else if(op<4)in(x),in(z),T1.change_son(x,z%P);
		else in(x),printf("%d\n",T1.ask_son(x));
	}
}
水管局长 LCT动态维护MST 4.4.3 树论综合
109 行
CPP JSON
【水管局长(LCT动态维护MST)】 树上问题算法模板。 核心函数: void in(int &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Query, Link_Cut_Tree, QAQ, Kruscal, QAQ 关键配置: N=1003,M=1e5+3 说明:freopen("123.txt","r",stdin);
C++ 108 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=1e5+3;
int n,m,x,y,z,T,op,id,id_O,v[N+M],vis[N+M],Ans[M],ID[N][N];
struct Query{int op,x,y;}Q[M];
inline void in(int &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N+M];
	struct QAQ{int mx,fa,tag,ps[2];}tr[N+M];
	inline void pushup(Re p){
		tr[p].mx=p;
		if(pl&&v[tr[pl].mx]>v[tr[p].mx])tr[p].mx=tr[pl].mx;
		if(pr&&v[tr[pr].mx]>v[tr[p].mx])tr[p].mx=tr[pr].mx;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p); 
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re x){access(x),splay(x),updata(x);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline void MST_link(Re x,Re y,Re id){
		makeroot(x);
		if(findroot(y)!=x)link(x,id),link(id,y);
		else{
			split(x,y);Re mx=tr[y].mx;
			if(v[id]<v[mx]){
				splay(mx);
				tr[tr[mx].ps[0]].fa=tr[tr[mx].ps[1]].fa=0;
				tr[mx].ps[0]=tr[mx].ps[1]=tr[mx].fa=0;
				link(x,id),link(id,y);
			}
		}
	}
	inline int MST_path(Re x,Re y){split(x,y);return v[tr[y].mx];}
}LCT;
struct Kruscal{
	int fa[N];
	struct QAQ{int x,y,z;inline bool operator<(const QAQ &O)const{return z<O.z;}}a[M];
	inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
	inline void sakura(){
		for(Re i=1;i<=n;++i)fa[i]=i;
		for(Re i=1;i<=m;++i)in(x),in(y),in(z),v[ID[x][y]=ID[y][x]=++id_O+n]=z,a[i]=(QAQ){x,y,z};
		for(Re i=1;i<=T;++i)in(op),in(x),in(y),vis[ID[x][y]]|=op>1,Q[i]=(Query){op,x,y};
		sort(a+1,a+m+1);
		for(Re i=1,t=0;t<n-1&&i<=m;++i)
			if(!vis[ID[x=a[i].x][y=a[i].y]]&&find(x)!=find(y))
				fa[find(x)]=find(y),++t,LCT.MST_link(x,y,ID[x][y]);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(T),T1.sakura();
	for(Re i=T;i>=1;--i){
		Re op=Q[i].op,x=Q[i].x,y=Q[i].y;
		if(op&1)Ans[++Ans[0]]=LCT.MST_path(x,y);
		else LCT.MST_link(x,y,ID[x][y]);
	}
	for(Re i=Ans[0];i>=1;--i)printf("%d\n",Ans[i]);
}
遥远的国度 LCT维护原子树信息 4.4.3 树论综合
88 行
CPP JSON
【遥远的国度(LCT维护原子树信息)】 树上问题算法模板。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void updata(Re p,Re v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 int nort(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=1e5+3,inf=2e9 说明:shi: ����ʵ����(�ڸ����ϵ�v);si: ���������������(���ڸ����ϵ�ans);freopen("123.txt","r",stdin);
C++ 87 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,x,y,z,T,op,root,X[N],Y[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	#define pv tr[p].v
	int Q[N];
	struct QAQ{int v,fa,si,shi,ans,add,tag,ans0,ps[2];multiset<int>SI;}tr[N];
	inline void pushup(Re p){
		tr[p].shi=min(pv,min(tr[pl].shi,tr[pr].shi));
		tr[p].si=min(*tr[p].SI.begin(),min(tr[pl].si,tr[pr].si));
		tr[p].ans=min(tr[p].shi,tr[p].si);
	}
	inline void updata(Re p){tr[p].tag^=1,swap(pl,pr);}
	inline void updata(Re p,Re v){tr[p].add=1,tr[p].shi=pv=v,tr[p].ans=min(tr[p].shi,tr[p].si);}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
		if(tr[p].add){
			if(pl)updata(pl,pv);
			if(pr)updata(pr,pv);
			tr[p].add=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf){
			splay(p);
			if(pr)tr[p].SI.insert(tr[pr].ans);
			pr=son;
			if(pr)tr[p].SI.erase(tr[p].SI.lower_bound(tr[pr].ans));
			pushup(p);
		}
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline void link(Re x,Re y){makeroot(x),access(y),splay(y),tr[tr[x].fa=y].SI.insert(tr[x].ans);}
	inline void change(Re x,Re y,Re z){makeroot(x),access(y),splay(y),updata(y,z);}
	inline int ask_son(Re p){access(p),splay(p);return min(pv,*tr[p].SI.begin());}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),T1.tr[0].shi=T1.tr[0].si=inf;
	for(Re i=1;i<n;++i)in(X[i]),in(Y[i]);
	for(Re i=1;i<=n;++i)in(T1.tr[i].v),T1.tr[i].SI.insert(inf),T1.pushup(i);
	for(Re i=1;i<n;++i)T1.link(X[i],Y[i]);
	in(root),T1.makeroot(root);
	while(T--){
		in(op),in(x);
		if(op<2)T1.makeroot(root=x);
		else if(op<3)in(y),in(z),T1.change(x,y,z),T1.makeroot(root);
		else printf("%d\n",T1.ask_son(x));
	}
}
长链剖分优化dp Dominant Indices 4.4.3 树论综合
46 行
CPP JSON
【长链剖分优化dp(Dominant Indices)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=1e6+3 说明:freopen("123.txt","r",stdin);
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3;
int n,m,x,y,o,Sz[N],son[N],Ans[N],dep[N],head[N];int *SZ=Sz,*dp[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs1(to,x);
			if(dep[to]>dep[son[x]])son[x]=to;
		}
	dep[x]=dep[son[x]]+1;
}
inline void dfs2(Re x,Re fa){
	dp[x][0]=1;
	if(son[x])dp[son[x]]=dp[x]+1,dfs2(son[x],x),Ans[x]=Ans[son[x]]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa&&to!=son[x]){
			dp[to]=SZ,SZ+=dep[to],dfs2(to,x);
			for(Re j=1;j<=dep[to];++j){
				dp[x][j]+=dp[to][j-1];
				if(dp[x][j]>dp[x][Ans[x]])Ans[x]=j;
				else if(dp[x][j]==dp[x][Ans[x]])Ans[x]=min(Ans[x],j);
			}
		}
	if(dp[x][Ans[x]]==1)Ans[x]=0;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs1(1,0),dp[1]=SZ,SZ+=dep[1],dfs2(1,0);
	for(Re i=1;i<=n;++i)printf("%d\n",Ans[i]);
}
Distance in Tree 长度等于K的路径数 4.4.3 树论综合
58 行
CPP JSON
【Distance in Tree(长度等于K的路径数)】 树上问题算法模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa) — 获取值 int calc(Re x,Re d) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=5e4+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,inf=2e9;
int n,m,o,x,y,K,head[N];LL Ans;
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa){
	if(dis[fa]+1>K)return;
	tmp[++cnt]=dis[x]=dis[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x);
}
inline int calc(Re x,Re d){
	Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])getdis(to,x);
	sort(tmp+1,tmp+cnt+1);
	Re L=cnt+1,R=cnt;
	for(Re i=1;i<=cnt&&i<R;++i){
		while(tmp[i]+tmp[L-1]>=K)--L;
		while(R>=L&&tmp[i]+tmp[R]>K)--R;
		if(L<=R&&i<R&&tmp[i]+tmp[L]==K&&tmp[i]+tmp[R]==K)ans+=(R-max(L,i+1)+1);
	}
	return ans;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,Ans+=calc(x,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			Ans-=calc(to,1),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%lld\n",Ans);
}
Qtree4 点分树+可删堆 4.4.3 树论综合
124 行
CPP JSON
【Qtree4(点分树+可删堆)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa,Re w) — 深度优先搜索遍历 void build(Re rt) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 int top(无参数) — 获取栈顶/堆顶元素 int sec(无参数) — 核心算法函数 核心结构体:QAQ, LCA, Queue 关键配置: N=1e5+3,logN=18,inf=1e9 说明:freopen("123.txt","r",stdin);
C++ 123 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,logN=18,inf=1e9;
int n,m,x,y,z,o,T,Cnt,A[N],ans[N],head[N];char op;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int O,lg[N<<1],fir[N],idx[N<<1],idd[N<<1],dis[N],deep[N],f[N<<1][20],ans[N<<1][20];
	inline void dfs(Re x,Re fa,Re w){
		idx[fir[x]=++O]=x,idd[O]=deep[x]=deep[fa]+1,dis[x]=dis[fa]+w;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)dfs(to,x,a[i].w),idx[++O]=x,idd[O]=deep[x];
	}
	inline void build(Re rt){
		dfs(rt,0,0),lg[0]=-1;
		for(Re i=1;i<=O;++i)f[i][0]=idd[i],ans[i][0]=idx[i],lg[i]=lg[i>>1]+1;
		for(Re j=1;j<=logN;++j)
			for(Re i=1;i+(1<<j)-1<=O;++i)
				if(f[i][j-1]<f[i+(1<<j-1)][j-1])f[i][j]=f[i][j-1],ans[i][j]=ans[i][j-1];
				else f[i][j]=f[i+(1<<j-1)][j-1],ans[i][j]=ans[i+(1<<j-1)][j-1];
	}
	inline int lca(Re x,Re y){
		Re L=fir[x],R=fir[y];
		if(L>R)swap(L,R);
		Re m=lg[R-L+1];
		return f[L][m]<f[R-(1<<m)+1][m]?ans[L][m]:ans[R-(1<<m)+1][m];
	}
}T0;
inline int Dis(Re x,Re y){return T0.dis[x]+T0.dis[y]-(T0.dis[T0.lca(x,y)]<<1);}
struct Queue{
	priority_queue<int>Q,D;
	inline int top(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty()?-inf:Q.top();
	}
	inline int sec(){
		Re x=top();if(x==-inf)return x;
		Q.pop();Re ans=top();Q.push(x);
		return ans;
	}
	inline void erase(Re x){if(Q.top()==x)Q.pop();else D.push(x);}
	inline void insert(Re x){Q.push(x);}
	inline int empty(){
		while(!Q.empty()&&!D.empty()&&Q.top()==D.top())Q.pop(),D.pop();
		return Q.empty();
	}
}Ans,Q[N],dis[N];
int rt,sum,Fa[N],vis[N],size[N],maxp[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re rt){
	dis[rt].insert(Dis(x,Fa[rt]));
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,rt);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,0,x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0);
			Fa[to=rt]=x,sakura(rt),Q[x].insert(dis[to].top());
		}
	Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
}
inline void insert(Re x){
	Ans.erase(ans[x]),Q[x].insert(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
	for(Re fa=x;Fa[fa];fa=Fa[fa]){
		Re pa=Fa[fa];
		Ans.erase(ans[pa]);
		if(!dis[fa].empty())Q[pa].erase(dis[fa].top());
		
		dis[fa].insert(Dis(x,pa));
		
		Q[pa].insert(dis[fa].top());
		Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
	}
}
inline void erase(Re x){
	Ans.erase(ans[x]),Q[x].erase(0),Ans.insert(ans[x]=max(0,Q[x].top()+Q[x].sec()));
	for(Re fa=x;Fa[fa];fa=Fa[fa]){
		Re pa=Fa[fa];
		Ans.erase(ans[pa]);
		Q[pa].erase(dis[fa].top());
		
		dis[fa].erase(Dis(x,pa));
		
		if(!dis[fa].empty())Q[pa].insert(dis[fa].top());
		Ans.insert(ans[pa]=max(0,Q[pa].top()+Q[pa].sec()));
	}
}
inline void change(Re x){
	if(A[x])insert(x),A[x]=0,++Cnt;
	else erase(x),A[x]=1,--Cnt;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1,Cnt=n;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	in(T),T0.build(1),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	while(T--){
		scanf(" %c",&op);
		if(op=='C')in(x),change(x);
		else if(!Cnt)puts("They have disappeared.");
		else printf("%d\n",Cnt<2?0:Ans.top());
	}
}
Race 长度等于K的路径最小边数 4.4.3 树论综合
56 行
CPP JSON
【Race(长度等于K的路径最小边数)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 void calc(Re x) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=2e5+3,INF=1e6+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,INF=1e6+3,inf=2e9;
int n,m,o,x,y,z,K,Ans,head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,dd[N],ddd[N],dep[N],Min[INF],tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>K)return;
	dd[++dd[0]]=dis[x]=dis[fa]+w,ddd[dd[0]]=dep[x]=dep[fa]+1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
	dis[x]=dep[x]=tmp[0]=0,Min[tmp[++tmp[0]]=0]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			dd[0]=0,getdis(to,x,a[i].w);
			for(Re i=1;i<=dd[0];++i)Ans=min(Ans,ddd[i]+Min[K-dd[i]]);
			for(Re i=1;i<=dd[0];++i)Min[dd[i]]=min(Min[dd[i]],ddd[i]),tmp[++tmp[0]]=dd[i];
		}
	for(Re i=1;i<=tmp[0];++i)Min[tmp[i]]=inf;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,calc(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	for(Re i=0;i<=K;++i)Min[i]=inf;
	while(m--)in(x),in(y),in(z),++x,++y,add(x,y,z),add(y,x,z);
	Ans=inf,sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%d\n",(Ans==inf)?-1:Ans);
}
点分树-在线求原树距离-BIT 求距离小于等于K的点权值之和 震波 4.4.3 树论综合
98 行
CPP JSON
【点分树-在线求原树距离-BIT(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 void build(Re N) — 构建数据结构(建树/建图) 核心结构体:QAQ, LCA, BIT 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 97 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int fa[N],top[N],son[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[son[x]]<size[to])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void build(){dfs1(1,0),dfs2(1,1);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
struct BIT{
	int n;vector<int>C;
	inline void build(Re N){C.resize((n=N)+1);}
	inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
	Re now=sum;vis[x]=1,fa[x]=Fa;
	TR1[x].build(now/2+1),TR2[x].build(now+1);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
	TR1[x].add(0,v);//subtree(x)
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);
		TR1[fa[i]].add(tmp,v);
		TR2[i].add(tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR1[x].ask(K);//subtree(x)
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
		ans+=TR1[fa[i]].ask(K-tmp);
		ans-=TR2[i].ask(K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-在线求原树距离-Seg 求距离小于等于K的点权值之和 震波 4.4.3 树论综合
113 行
CPP JSON
【点分树-在线求原树距离-Seg(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re Fa) — 深度优先搜索遍历 void dfs2(Re x,Re rt) — 深度优先搜索遍历 void build(无参数) — 构建数据结构(建树/建图) int lca(Re x,Re y) — 查询最近公共祖先 int Dis(Re x,Re y) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 核心结构体:QAQ, LCA, Segment_Tree, QAQ 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 112 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct LCA{
	int fa[N],top[N],son[N],size[N];
	inline void dfs1(Re x,Re Fa){
		size[x]=1,deep[x]=deep[fa[x]=Fa]+1;
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=Fa){
				dfs1(to,x),size[x]+=size[to];
				if(size[son[x]]<size[to])son[x]=to;
			}
	}
	inline void dfs2(Re x,Re rt){
		top[x]=rt;
		if(!son[x])return;
		dfs2(son[x],rt);
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to);
	}
	inline void build(){dfs1(1,0),dfs2(1,1);}
	inline int lca(Re x,Re y){
		while(top[x]!=top[y]){
			if(deep[top[x]]<deep[top[y]])swap(x,y);
			x=fa[top[x]];
		}
		if(deep[x]>deep[y])swap(x,y);
		return x;
	}
}T1;
inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}
int pt[N<<1];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid (L+R>>1)
	int O;
	struct QAQ{int S,lp,rp;}tr[N*60];
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].S+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		tr[p].S=tr[pl].S+tr[pr].S;
	}
	inline int ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		Re ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
}TR;
int rt,sum,fa[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void sakura(Re x,Re Fa){
	Re now=sum;vis[x]=1,fa[x]=Fa;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);
}
inline void change(Re x,Re v){
	TR.change(pt[x],0,n,0,v);
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);
		TR.change(pt[fa[i]],0,n,tmp,v);
		TR.change(pt[i+n],0,n,tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR.ask(pt[x],0,n,0,K);
	for(Re i=x;fa[i];i=fa[i]){
		Re tmp=Dis(x,fa[i]);if(tmp>K)continue;
		ans+=TR.ask(pt[fa[i]],0,n,0,K-tmp);
		ans-=TR.ask(pt[i+n],0,n,0,K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-预处理原树距离-BIT 求距离小于等于K的点权值之和 震波 4.4.3 树论综合
75 行
CPP JSON
【点分树-预处理原树距离-BIT(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void build(Re N) — 构建数据结构(建树/建图) void add(Re x,Re v) — 加法更新 int ask(Re x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 核心结构体:QAQ, BIT 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct BIT{
	int n;vector<int>C;
	inline void build(Re N){C.resize((n=N)+1);}
	inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR1[N],TR2[N];
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	TR1[x].build(now/2+1),TR2[x].build(now+1);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
	TR1[x].add(0,v);//subtree(x)
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		TR1[frt[x][i-1]].add(tmp,v);
		TR2[frt[x][i]].add(tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR1[x].ask(K);//subtree(x)
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];if(tmp>K)continue;
		ans+=TR1[frt[x][i-1]].ask(K-tmp);
		ans-=TR2[frt[x][i]].ask(K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分树-预处理原树距离-Seg 求距离小于等于K的点权值之和 震波 4.4.3 树论综合
90 行
CPP JSON
【点分树-预处理原树距离-Seg(求距离小于等于K的点权值之和 震波)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void change(Re &p,Re L,Re R,Re x,Re v) — 核心算法函数 int ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 void change(Re x,Re v) — 核心算法函数 核心结构体:QAQ, Segment_Tree, QAQ 关键配置: N=1e5+3,inf=2e9,logN=17 说明:freopen("123.txt","r",stdin);
C++ 89 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9,logN=17;
int n,m,o,x,y,T,op,lastans,A[N],head[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int pt[N<<1];
struct Segment_Tree{
	#define pl tr[p].lp
	#define pr tr[p].rp
	#define mid (L+R>>1)
	int O;
	struct QAQ{int S,lp,rp;}tr[N*60];
	inline void change(Re &p,Re L,Re R,Re x,Re v){
		if(!p)p=++O;
		if(L==R){tr[p].S+=v;return;}
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		tr[p].S=tr[pl].S+tr[pr].S;
	}
	inline int ask(Re p,Re L,Re R,Re l,Re r){
		if(!p)return 0;
		if(l<=L&&R<=r)return tr[p].S;
		Re ans=0;
		if(l<=mid)ans+=ask(pl,L,mid,l,r);
		if(r>mid)ans+=ask(pr,mid+1,R,l,r);
		return ans;
	}
}TR;
int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);
}
inline void change(Re x,Re v){
	TR.change(pt[x],0,n,0,v);
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		TR.change(pt[frt[x][i-1]],0,n,tmp,v);
		TR.change(pt[frt[x][i]+n],0,n,tmp,v);
	}
}
inline int ask(Re x,Re K){
	Re ans=TR.ask(pt[x],0,n,0,K);
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];if(tmp>K)continue;
		ans+=TR.ask(pt[frt[x][i-1]],0,n,0,K-tmp);
		ans-=TR.ask(pt[frt[x][i]+n],0,n,0,K-tmp);
	}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),add(x,y),add(y,x);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=n;++i)change(i,A[i]);
	while(T--){
		in(op),in(x),in(y),x^=lastans,y^=lastans;
		if(op)change(x,y-A[x]),A[x]=y;
		else printf("%d\n",lastans=ask(x,y));
	}
}
点分治 (询问是否有长度等于K的路径) 分各子树求解 4.4.3 树论综合
58 行
CPP JSON
【点分治 (询问是否有长度等于K的路径)(分各子树求解)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 void calc(Re x) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=1e4+3,M=103,INF=1e7+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e4+3,M=103,INF=1e7+3,inf=2e9;
int n,m,o,x,y,z,T,maxK,K[M],Ans[M],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,dd[N],vis[N],tmp[N],dis[N],maxp[N],size[N];bool judge[INF];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>maxK)return;
	dd[++dd[0]]=dis[x]=dis[fa]+w;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline void calc(Re x){
	tmp[0]=0,judge[tmp[++tmp[0]]=0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]){
			dis[x]=dd[0]=0,getdis(to,x,a[i].w);
			for(Re j=1;j<=dd[0];++j)
				for(Re k=1;k<=T;++k)
					if(K[k]>=dd[j])Ans[k]|=judge[K[k]-dd[j]];
			for(Re j=1;j<=dd[0];++j)judge[tmp[++tmp[0]]=dd[j]]=1;
		}
	for(Re i=1;i<=tmp[0];++i)judge[tmp[i]]=0;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,calc(x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	for(Re i=1;i<=T;++i)in(K[i]),maxK=max(maxK,K[i]);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	for(Re i=1;i<=T;++i)puts(Ans[i]?"AYE":"NAY");
}
点分治 (长度小于等于K的路径数 Tree) 容斥 4.4.3 树论综合
58 行
CPP JSON
【点分治 (长度小于等于K的路径数 Tree)(容斥)】 点分治/边分治模板,用于树上路径统计问题。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re fa,Re w) — 获取值 int calc(Re x,Re d) — 计算函数 void sakura(Re x) — 后缀数组 核心结构体:QAQ 关键配置: N=4e4+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,inf=2e9;
int n,m,o,x,y,z,K,head[N];LL Ans;
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int rt,sum,cnt,tmp[N],dis[N],vis[N],maxp[N],size[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re fa,Re w){
	if(dis[fa]+w>K)return;
	tmp[++cnt]=dis[x]=dis[fa]+w;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,a[i].w);
}
inline int calc(Re x,Re d){
	Re ans=0;cnt=0,tmp[++cnt]=dis[x]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])getdis(to,x,a[i].w);
	sort(tmp+1,tmp+cnt+1);
	Re R=cnt;
	for(Re i=1;i<=cnt&&i<R;++i){
		while(i<R&tmp[i]+tmp[R]>K)--R;
		if(i<R)ans+=(R-(i+1)+1);
	}
	return ans;
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,Ans+=calc(x,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			Ans-=calc(to,a[i].w),sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,x),sakura(rt);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	in(K);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt);
	printf("%lld\n",Ans);
}
幻想乡战略游戏 点分树 4.4.3 树论综合
76 行
CPP JSON
【幻想乡战略游戏(点分树)】 树上问题算法模板。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void getrt(Re x,Re fa) — 获取值 void getdis(Re x,Re rt,Re fa,Re d) — 获取值 void sakura(Re x) — 后缀数组 void change(Re x,Re v) — 核心算法函数 LL ask(Re x) — 核心算法函数 核心结构体:QAQ, TREE, QAQ 关键配置: N=1e5+3,inf=2e9 说明:freopen("123.txt","r",stdin);
C++ 75 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,inf=2e9;
int n,m,o,x,y,z,T,root,A[N],head[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct TREE{
	int o,head[N];
	struct QAQ{int rt,to,next;}a[N];
	inline void add(Re x,Re y,Re z){a[++o].rt=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
}T0;
int rt,sum,Sv[N],gs[N],vis[N],size[N],maxp[N],frt[N][20],fdis[N][20];LL Sdv1[N],Sdv2[N];
inline void getrt(Re x,Re fa){
	size[x]=1,maxp[x]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)
			getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]);
	maxp[x]=max(maxp[x],sum-size[x]);
	if(maxp[x]<maxp[rt])rt=x;
}
inline void getdis(Re x,Re rt,Re fa,Re d){
	if(x!=rt)frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+a[i].w);
}
inline void sakura(Re x){
	Re now=sum;vis[x]=1,getdis(x,x,0,0);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!vis[to=a[i].to])
			sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),T0.add(x,to,rt),sakura(rt);
}
inline void change(Re x,Re v){
	Sdv1[x]+=v*0,Sv[x]+=v;
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		Sdv1[frt[x][i-1]]+=(LL)v*tmp;
		Sdv2[frt[x][i]]+=(LL)v*tmp;
		Sv[frt[x][i-1]]+=v;
	}
}
inline LL ask(Re x){
	LL ans=Sdv1[x];
	for(Re i=gs[x];i>=2;--i){
		Re tmp=fdis[x][i-1];
		ans+=Sdv1[frt[x][i-1]];
		ans-=Sdv2[frt[x][i]];
		ans+=(LL)(Sv[frt[x][i-1]]-Sv[frt[x][i]])*tmp;
	}
	return ans;
}
inline LL find(Re x){
	LL tmp=ask(x);
	for(Re i=T0.head[x];i;i=T0.a[i].next)
		if(ask(T0.a[i].to)<tmp)return find(T0.a[i].rt);
	return tmp;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(root=rt);
	for(Re i=1;i<=n;++i)frt[i][++gs[i]]=i;
	while(T--)in(x),in(y),change(x,y),printf("%lld\n",find(root));
}
Kruskal 重构树 KruskalReconstructionTree 4.4.4 Kruskal重构树
134 行
CPP JSON
【Kruskal 重构树(Kruskal Reconstruction Tree)】 ▪ KruskalReconstructionTree — 结构体封装: — n(原图节点数)、tot(重构树总节点数 = 2N-1) — g[][](树邻接表)、val[](节点权值,叶子为 0,虚拟节点为合并时的边权) — build(edges) — 按边权排序后 Kruskal 建树:每次合并 u,v 时新建节点 tot,权值为边权,将 u,v 所在连通块的根作为 tot 的子节点 — lca(u, v) — 查询 u,v 在重构树上的 LCA,其权值即为原图 u↔v 路径上最大边权的最小值 适用于瓶颈路径问题(最小化路径最大边权),可将瓶颈查询转化为 LCA 查询。
C++ 134 行 CPP
struct KruskalReconstructionTree {
    int n;                      // 原图节点数
    int tot;                    // 重构树总节点数
    vector<vector<int>> g;      // 树邻接表
    vector<int> val;            // 节点权值 (原节点 -1)
    vector<int> parent;         // 父节点
    vector<int> dsu;            // 并查集

    static const int LOG = 20;  // 倍增 LCA 参数
    vector<int> depth;
    vector<vector<int>> up;

    KruskalReconstructionTree(int n_) : n(n_) {
        tot = n;
        g.resize(2 * n);
        val.resize(2 * n);
        parent.assign(2 * n, -1);
        dsu.resize(2 * n);
        iota(dsu.begin(), dsu.end(), 0);
        for (int i = 0; i < n; i++) val[i] = -1;
        depth.resize(2 * n);
    }

    int find(int x) {
        while (dsu[x] != x) dsu[x] = dsu[dsu[x]], x = dsu[x];
        return x;
    }

    // 构建重构树。edges: {u,v,w}
    void build(vector<tuple<int, int, int>> edges, bool sorted = false) {
        if (!sorted) {
            sort(edges.begin(), edges.end(),
                 [](const auto &a, const auto &b) {
                     return get<2>(a) > get<2>(b); // 最大瓶颈路
                 });
        }
        for (auto &[u, v, w] : edges) {
            int ru = find(u), rv = find(v);
            if (ru == rv) continue;
            int node = tot++;
            val[node] = w;
            g[node].push_back(ru);
            g[node].push_back(rv);
            parent[ru] = parent[rv] = node;
            dsu[ru] = dsu[rv] = node;
            dsu[node] = node;
            if (tot >= (int)g.size()) {
                g.resize(tot + 5);
                val.resize(tot + 5);
                parent.resize(tot + 5);
                depth.resize(tot + 5);
            }
        }
        g.resize(tot);
        val.resize(tot);
        parent.resize(tot);
        // 建立倍增表
        initLCA();
    }

    void initLCA() {
        depth.assign(tot, 0);
        up.assign(tot, vector<int>(LOG, -1));
        for (int i = 0; i < tot; i++)
            if (parent[i] == -1) dfs(i, -1);
    }

    void dfs(int u, int p) {
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            if (up[u][j - 1] != -1)
                up[u][j] = up[up[u][j - 1]][j - 1];
            else
                up[u][j] = -1;
        }
        for (int v : g[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    // 查询 u, v 的 LCA
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if (diff >> j & 1) u = up[u][j];
        }
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }

    // 查询原图 u->v 瓶颈路(最小边权的最大值)
    int queryMaxEdgeMin(int u, int v) {
        int w = lca(u, v);
        if (w == -1) return -1;
        return val[w];
    }

    // 从 s 出发,仅走边权 ≤ lim 的边能到达的所有节点
    vector<int> queryReachable(int s, int lim) {
        int u = s;
        for (int j = LOG - 1; j >= 0; j--)
            if (up[u][j] != -1 && val[up[u][j]] <= lim)
                u = up[u][j];
        vector<int> res;
        collectLeaves(u, -1, res);
        return res;
    }

    // 从 s 出发,仅走边权 ≥ lim 的边能到达的所有节点(需降序构建)
    vector<int> queryReachableMin(int s, int lim) {
        int u = s;
        for (int j = LOG - 1; j >= 0; j--)
            if (up[u][j] != -1 && val[up[u][j]] >= lim)
                u = up[u][j];
        vector<int> res;
        collectLeaves(u, -1, res);
        return res;
    }

    // 收集子树中所有原图节点
    void collectLeaves(int u, int p, vector<int> &out) {
        if (u < n) { out.push_back(u); return; }
        for (int v : g[u]) if (v != p) collectLeaves(v, u, out);
    }
};
Crash的文明世界 树形dp 4.4.5 树形DP
54 行
CPP JSON
【Crash的文明世界(树形dp)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 void Stirling(Re N) — 核心算法函数 核心结构体:QAQ 关键配置: N=5e4+3,M=153,P=10007 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e4+3,M=153,P=10007;
int n,m,x,y,o,K,jc[M],fto[M],head[N],S[M][M],f[N][M],g[N][M];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int dp=0;x=0;char c=getchar();
    while(c<'0'||c>'9')dp|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=dp?-x:x;
}
inline void dfs1(Re x,Re fa){
	f[x][0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs1(to,x),(f[x][0]+=f[to][0])%=P;
			for(Re j=1;j<=K;++j)(f[x][j]+=(f[to][j]+f[to][j-1])%P)%=P;
		}
}
inline void dfs2(Re x,Re fa){
	if(fa){
		fto[0]=(g[fa][0]+f[fa][0]-f[x][0]+P)%P;
		for(Re j=1;j<=K;++j)fto[j]=(g[fa][j]+f[fa][j]-(f[x][j]+f[x][j-1])%P+P)%P;
		g[x][0]=fto[0];
		for(Re j=1;j<=K;++j)g[x][j]=(fto[j]+fto[j-1])%P;
	}
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)dfs2(to,x);
}
inline void Stirling(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=(S[j-1][i-1]+j*S[j][i-1]%P)%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs1(1,0),dfs2(1,0),Stirling(K),jc[0]=1;
	for(Re i=1;i<=K;++i)jc[i]=jc[i-1]*i%P;
	for(Re i=1;i<=n;++i){
		Re ans=0;
		for(Re j=0;j<=K;++j)
			(ans+=S[j][K]*jc[j]%P*(f[i][j]+g[i][j])%P)%=P;
		printf("%d\n",ans);
	}
}
换根dp Great Cow Gathering 4.4.5 树形DP
34 行
CPP JSON
【换根dp(Great Cow Gathering)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs1(Re x,Re fa) — 深度优先搜索遍历 void dfs2(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 33 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const LL N=1e5+3,inf=1e18;
int n,m,x,y,z,o,A[N],S[N],dis[N],size[N],head[N];LL ans=inf,f[N],g[N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs1(Re x,Re fa){
	size[x]=1,S[x]=A[x];
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)
		dis[to]=a[i].w,dfs1(to,x),S[x]+=S[to],size[x]+=size[to],f[x]+=f[to]+(LL)S[to]*a[i].w;
}
inline void dfs2(Re x,Re fa){
	if(fa)g[x]=g[fa]+f[fa]-f[x]-(LL)S[x]*dis[x]+(LL)(S[1]-S[x])*dis[x];
	for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)dfs2(to,x);
	ans=min(ans,f[x]+g[x]);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),m=n-1;
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	dfs1(1,0),dfs2(1,0),printf("%lld\n",ans);
}
树形dp 没有上司的舞会 4.4.5 树形DP
28 行
CPP JSON
【树形dp(没有上司的舞会)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(int x,int y) — 加法更新 void dfs(int w) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 27 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010];
struct QAQ{int next,to;}Q[6010];
inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;}
inline void dfs(int w){
    for(R k=head[w];k;k=Q[k].next){
        int to=Q[k].to;
        dfs(to);
        f[w][0]+=max(f[to][0],f[to][1]);
        f[w][1]+=f[to][0];
    }
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&f[i][1]);
    for(i=1;i<n;i++)scanf("%d%d",&a,&b),pan[a]++,add(b,a);
    for(i=1;i<=n;i++)
        if(!pan[i]){
            dfs(i);
            printf("%d\n",max(f[i][0],f[i][1]));
            return 0;
        }
}
保安站岗,皇宫看守 树形dp 4.4.5 树形DP
37 行
CPP JSON
【保安站岗,皇宫看守(树形dp)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(int x,int y) — 加法更新 void dfs(int x) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 36 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define R register int
using namespace std;
struct QAQ{int to,next;}a[1505]; 
int m,pan[1505],n,t,w[1505],dp[1505][3],head[1505];
inline void add(int x,int y){a[++t].to=y,a[t].next=head[x],head[x]=t;}
  //dp[i][0] 以及各种情况的具体转移方程和初始状态 
inline void dfs(int x){
    R i,to,dd=0xfffffff;
    dp[x][1]=w[x];dp[x][2]=0;dp[x][0]=0;
    for(i=head[x];i;i=a[i].next){
        dfs(to=a[i].to);
        dd=min(dd,dp[to][1]-min(dp[to][0],dp[to][1]));
        dp[x][0]+=min(dp[to][0],dp[to][1]);
        dp[x][1]+=min(dp[to][1],dp[to][2]);
        dp[x][2]+=min(dp[to][0],dp[to][1]);
    }
    dp[x][0]+=dd;
}
int main(){
	memset(dp,127,sizeof(dp));
    scanf("%d",&n);
    R i,j,a,k,r;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a,&k,&m);w[a]=k;
        for(j=1;j<=m;j++)scanf("%d",&r),pan[r]=1,add(a,r);
    }
    for(i=1;i<=n;i++)
        if(!pan[i]){
            dfs(i);
            printf("%d",min(dp[i][1],dp[i][0]));
            return 0;
        }
}
树上背包优化O复杂度 (NOI Online 2 游戏) nk 4.4.5 树形DP
73 行
CPP JSON
【树上背包优化O复杂度 (NOI Online 2 游戏)(nk)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void dfs0(Re x,Re fa) — 深度优先搜索遍历 void dfs(Re x,Re fa) — 深度优先搜索遍历 int C(Re m,Re n) — 核心算法函数 核心结构体:QAQ 关键配置: N=5003,P=998244353 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 72 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5003,P=998244353;
int n,m,o,x,y,f[N],g[N],A[N],jc[N],head[N];char s[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int sz1[N],sz0[N],lim[N],dp[N][N],tmp[N];
inline void dfs0(Re x,Re fa){
	sz0[x]=(!A[x]),sz1[x]=A[x];
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa)dfs0(to,x),sz1[x]+=sz1[to],sz0[x]+=sz0[to];
//	lim[x]=min(sz1[x],size[x]-sz1[x]);
}
inline void dfs(Re x,Re fa){
	dp[x][0]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x);
			for(Re j=0;j<=lim[x]+lim[to];++j)tmp[j]=0;
			for(Re j=lim[x];j>=0;--j)
				for(Re k=lim[to];k>=0;--k)
					(tmp[j+k]+=(LL)dp[x][j]*dp[to][k]%P)%=P;
			lim[x]+=lim[to];
			for(Re j=0;j<=lim[x];++j)dp[x][j]=tmp[j];
		}
	++lim[x];
	if(A[x])for(Re j=min(lim[x],sz0[x]);j>=1;--j)
		(dp[x][j]+=(LL)dp[x][j-1]*(sz0[x]-(j-1))%P)%=P;
	else for(Re j=min(lim[x],sz1[x]);j>=1;--j)
		(dp[x][j]+=(LL)dp[x][j-1]*(sz1[x]-(j-1))%P)%=P;
	while(!dp[x][lim[x]])--lim[x];
}
inline int C(Re m,Re n){return (LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;}
int main(){
//	freopen("match.in","r",stdin);
//	freopen("match.out","w",stdout);
	in(n),scanf("%s",s+1),m=n-1,jc[0]=1;
	for(Re i=1;i<=n;++i)A[i]=s[i]-'0',jc[i]=(LL)jc[i-1]*i%P;
	while(m--)in(x),in(y),add(x,y),add(y,x);
	dfs0(1,0),dfs(1,0);
//	for(Re i=1;i<=n;++i)printf("lim[%d]=%d\n",i,lim[i]);
//	for(Re i=0;i<=n/2;++i)printf("dp[%d]=%d\n",i,dp[1][i]);
//	for(Re j=0;j<=lim[1];++j)printf("%d ",dp[1][j]);
	for(Re j=0;j<=lim[1];++j)g[j]=(LL)dp[1][j]*jc[n/2-j]%P;
	for(Re i=lim[1];i>=0;--i){
		f[i]=g[i];
		for(Re j=i+1;j<=lim[1];++j)f[i]=(f[i]-(LL)C(i,j)*f[j]%P+P)%P;
	}
	for(Re i=0;i<=n/2;++i)printf("%d\n",f[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
树上背包优化O复杂度 (树上染色) nk 4.4.5 树形DP
40 行
CPP JSON
【树上背包优化O复杂度 (树上染色)(nk)】 树形 DP 模板,在树上进行 DFS 递推动态规划。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=2003 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:树上的最优化问题(最大独立集、最小支配集、直径等)
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003;
int n,m,x,y,z,o,K,size[N],head[N];LL tmp[N],dp[N][N];
struct QAQ{int w,to,next;}a[N<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void dfs(Re x,Re fa){
	size[x]=1,dp[x][0]=dp[x][1]=0;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)!=fa){
			dfs(to,x);
			for(Re j=0;j<=size[x]+size[to];++j)tmp[j]=dp[0][0];
			for(Re j=size[x];j>=0;--j)
				if(dp[x][j]>=0)for(Re k=size[to];k>=0;--k)
					if(dp[to][k]>=0)
						tmp[j+k]=max(tmp[j+k],dp[x][j]+dp[to][k]+
							(LL)a[i].w*((LL)k*(K-k)+(LL)(size[to]-k)*(n-size[to]-(K-k)))
						);
			size[x]+=size[to];
			for(Re j=0;j<=size[x];++j)dp[x][j]=tmp[j];
		}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),m=n-1;
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	memset(dp,-20,sizeof(dp));
	dfs(1,0),printf("%lld\n",dp[1][K]);
}
已复制