【数据结构】点分治 点分树

求树上长度小于等于k的路径

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 10010, M = N * 2;int n, m;
int h[N], e[M], w[M], ne[M], idx; //邻接表
bool st[N]; //记录每个点是否被删掉
int p[N]; //存储当前重心的所有子树中所有节点之间的所有距离
int q[N]; //存储当前子树中所有节点之间的所有距离void add(int a, int b, int c) //添加边
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int get_size(int u, int fa) //求以 u 为根的子树大小
{if(st[u]) return 0; //被删掉的节点不考虑int res = 1; //记录节点数for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;res += get_size(j, u);}return res;
}//tot 表示当前整棵树的大小
//求重心 wc（并不一定是重心，只要保证删掉 wc 每个子树的大小 <= tot / 2 即可），并返回当前子树大小
int get_wc(int u, int fa, int tot, int &wc)
{if(st[u]) return 0; //如果当前点已经被删除，直接返回int sum = 1, ms = 0; //sum 表示当前子树的节点数，ms 表示去掉当前点剩余子树的节点最大值for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;int t = get_wc(j, u, tot, wc);ms = max(ms, t);sum += t;}ms = max(ms, tot - sum);if(ms <= tot / 2) wc = u; //如果子树的节点最大值 <= tot / 2，说明找到一个 “重心”return sum;
}//求一下 u 所在子树中每个点里到重心的距离，u 到重心的距离为 dist
void get_dist(int u, int fa, int dist, int &qt)
{if(st[u]) return;q[qt++] = dist;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;get_dist(j, u, dist + w[i], qt);}
}int get(int a[], int k) //求长度为 k 的数组 a 中相加和 <= m 的数对个数
{sort(a, a + k); //先将 a 数组从小到大排序int res = 0; //记录总方案数for(int i = k - 1, j = -1; i >= 0; i--){while(j + 1 < i && a[j + 1] + a[i] <= m) j++;j = min(j, i - 1); //j 最多只能到 i - 1res += j + 1; //累加方案数}return res;
}int calc(int u) //点分治
{if(st[u]) return 0; //如果当前点已经被删除，直接返回int res = 0; //记录答案get_wc(u, -1, get_size(u, -1), u); //找重心st[u] = true; //删除重心//归并处理所有子树int pt = 0; //记录 p 数组的大小for(int i = h[u]; i != -1; i = ne[i]){int j = e[i], qt = 0; //qt 表示 q 数组的大小get_dist(j, -1, w[i], qt); //求一下 j 所在子树中每个点里到重心的距离，并存到 q 数组中res -= get(q, qt); //减去当前子树中不符合条件的路径条数for(int k = 0; k < qt; k++){if(q[k] <= m) res++; //加上所有到重心的距离 <= m 的路径p[pt++] = q[k]; //将当前子树中的路径全部加入 p 数组}}res += get(p, pt); //加上所有端点在不同子树的合法路径条数for(int i = h[u]; i != -1; i = ne[i]) res += calc(e[i]); //递归处理每棵子树内部的路径return res;
}int main()
{while(scanf("%d%d", &n, &m), n || m){memset(h, -1, sizeof h); //初始化邻接表memset(st, 0, sizeof st); //清空标记数组for(int i = 0; i < n - 1; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c); //无向边}printf("%d\n", calc(0)); //点分治}return 0;
}

264. 权值

给定一棵 NN 个节点的树，每条边带有一个权值。

求一条简单路径，路径上各条边的权值和等于 KK，且路径包含的边的数量最少。

输入格式

第一行两个整数 N,KN,K。

第 2∼N2∼N 行每行三个整数 x,y,zx,y,z，表示一条无向边的两个端点 x,yx,y 和权值 zz，点的编号从 00 开始。

输出格式

输出一个整数，表示最少边数量。

如果不存在满足要求的路径，输出 −1−1。

数据范围

1≤N≤2×1051≤N≤2×105,
1≤K≤1061≤K≤106,
0≤z≤1060≤z≤106

输入样例：

Copy

4 3
0 1 1
1 2 2
1 3 4

输出样例：

Copy

2

#include <iostream>
#include <cstring>using namespace std;typedef pair<int, int> PII;const int N = 200010, M = N * 2, S = 1000010, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
//p[i] 存储所有子树中的每个点到重心的距离和边数
//q[i] 存储当前子树中的每个点到重心的距离和边数
PII p[N], q[N];
int f[S]; //f[i] 表示前面所有子树中到重心距离为 i 的路径的边数最小值
int res = INF; //记录答案void add(int a, int b, int c) //添加边
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int get_size(int u, int fa) //求 u 所在子树的大小
{if(st[u]) return 0;int res = 1;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;res += get_size(j, u);}return res;
}int get_wc(int u, int fa, int tot, int &wc) //求重心，并返回子树大小
{if(st[u]) return 0;int sum = 1, ms = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;int t = get_wc(j, u, tot, wc);ms = max(ms, t);sum += t;}ms = max(ms, tot - sum);if(ms <= tot / 2) wc = u;return sum;
}//求一下当前子树中的所有点到重心的距离和边数
//dist 表示 u 到重心的距离
//cnt 表示 u 到重心的边数
void get_dist(int u, int fa, int dist, int cnt, int &qt)
{if(st[u] || dist > m) return; //被删的点、到重心的距离 > m 的点不需要考虑q[qt++] = {dist, cnt};for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;get_dist(j, u, dist + w[i], cnt + 1, qt);}
}void calc(int u) //点分治
{if(st[u]) return;get_wc(u, -1, get_size(u, -1), u); //求重心st[u] = true; //将重心删去//归并子树之间的信息int pt = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];int qt = 0;get_dist(j, -1, w[i], 1, qt); //求一下当前子树中的所有点到重心的距离和边数for(int k = 0; k < qt; k++){auto &t = q[k];if(t.first == m) res = min(res, t.second); //更新第三类路径res = min(res, f[m - t.first] + t.second); //更新第二类路径p[pt++] = t; //将当前节点存入整棵子树的数组中}for(int k = 0; k < qt; k++) //用当前子树的信息更新 f{auto &t = q[k];f[t.first] = min(f[t.first], t.second);}}for(int i = 0; i < pt; i++)  f[p[i].first] = INF; //重置 ffor(int i = h[u]; i != -1; i = ne[i]) calc(e[i]); //递归处理每棵子树
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h); //初始化邻接表for(int i = 0; i < n - 1; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c); //无向边}memset(f, 0x3f, sizeof f); //初始化 fcalc(0); //点分治if(res == INF) res = -1; //如果 res = INF，说明无解printf("%d\n", res);return 0;
}

2226. 开店

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

MarkDown视图Copy

风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。

最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。

这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。

很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 nn 个地方，编号为 11 到 nn，被 n−1n−1 条带权的边连接起来。

每个地方都住着一个妖怪，其中第 ii 个地方的妖怪年龄是 xixi。

妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。

所以这个树所有顶点的度数都小于或等于 33。

妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 1818 岁少女幽香和八云紫就比较喜欢可爱的东西。

幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 uu（uu为编号），然后在 uu 开一家面向年龄在 LL 到 RR 之间（即年龄大于等于 LL、小于等于 RR）的妖怪的店。

也有可能 uu 这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 LL 到 RR 之间的妖怪，到点 uu 的距离的和是多少（妖怪到 uu 的距离是该妖怪所在地方到 uu 的路径上的边的权之和），幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

输入格式

第一行三个用空格分开的数 n、Qn、Q 和 AA，表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行 nn 个用空格分开的数 x1、x2、…、xnx1、x2、…、xn，xixi 表示第 ii 个地点妖怪的年龄，满足 0<=xi<A0<=xi<A。(年龄是可以为 00 的，例如刚出生的妖怪的年龄为 00。)

接下来 n−1n−1 行，每行三个用空格分开的数 a、b、ca、b、c，表示树上的顶点 aa 和 bb 之间有一条权为 cc 的边，aa 和 bb 是顶点编号。

接下来 QQ 行，每行三个用空格分开的数 u、a、bu、a、b。对于这 QQ 行的每一行，用 a、b、Aa、b、A 计算出 LL 和 RR，表示询问“在地方 uu 开店，面向妖怪的年龄区间为 [L,R][L,R] 的方案的方便值是多少”。

对于其中第 11 行，LL 和 RR 的计算方法为：L=min(a%A,b%A)L=min(a%A,b%A), R=max(a%A,b%A)R=max(a%A,b%A)。

对于第 22 到第 QQ 行，假设前一行得到的方便值为 ansans，那么当前行的 LL 和 RR 计算方法为： L=min((a+ans)%A,(b+ans)%A)L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)R=max((a+ans)%A,(b+ans)%A)。

输出格式

对于每个方案，输出一行表示方便值。

数据范围

1≤n≤1500001≤n≤150000,
1≤Q≤2000001≤Q≤200000,
1≤A≤1091≤A≤109,
1≤c≤10001≤c≤1000

输入样例：

Copy

10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4

输出样例：

Copy

1603
957
7161
9466
3232
5223
1879
1669
1282
0

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 150010, M = N * 2;int n, m, A;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int age[N]; //存储每个节点的年龄
bool st[N]; //记录每个节点是否被删掉
struct Father
{int u, num; //记录每个节点在它所在的子树的重心 u 的第 num 个儿子中LL dist; //记录每个节点到重心 u 的距离
}; //存储每个节点关于父节点的信息
vector<Father> f[N]; //对于每个节点都要存储若干个父节点的信息
struct Son
{int age; //记录当前节点的年龄LL dist; //记录当前节点到重心的距离bool operator< (const Son &t) const{return age < t.age;}
};
vector<Son> son[N][3]; //对于每个节点最多有 3 棵子树，需要存储每棵子树中所有节点的信息void add(int a, int b, int c) //添加边
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int get_size(int u, int fa) //求 u 所在子树的大小
{if(st[u]) return 0; //如果 u 已经被删掉，直接返回int res = 1;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;res += get_size(j, u);}return res;
}int get_wc(int u, int fa, int tot, int &wc) //求重心
{if(st[u]) return 0; //如果 u 已经被删掉，直接返回int sum = 1, ms = 0; //记录 u 所在子树大小，ms 表示所有子树的最大节点数for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;int t = get_wc(j, u, tot, wc);ms = max(ms, t);sum += t;}ms = max(ms, tot - sum);if(ms <= tot / 2) wc = u;return sum;
}//dist 表示 u 到重心的距离
//wc 表示重心
//k 表示 u 是 wc 的第几棵子树
void get_dist(int u, int fa, LL dist, int wc, int k, vector<Son> &p) //将 u 的第 k 个子树中所有节点存储 p
{if(st[u]) return; //如果 u 已经被删掉，直接返回f[u].push_back({wc, k, dist}); //存储重心信息p.push_back({age[u], dist}); //存储子节点信息for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;get_dist(j, u, dist + w[i], wc, k, p);}
}void calc(int u) //构建点分树
{if(st[u]) return; //如果 u 已经被删掉，直接返回get_wc(u, -1, get_size(u, -1), u); //求重心st[u] = true; //将重心删掉for(int i = h[u], k = 0; i != -1; i = ne[i]) //k 表示当前子树的编号{int j = e[i];if(st[j]) continue; //如果 j 已经被删掉，说明它已经作为重心出现在前面，不再考虑auto &p = son[u][k]; //当前子树对应的容器p.push_back({-1, 0}), p.push_back({A + 1, 0}); //加入两个哨兵，防止边界情况get_dist(j, -1, w[i], u, k, p); //将子树中所有点存储对应的容器中k++;sort(p.begin(), p.end()); //将子树中所有节点按照年龄排序for(int i = 1; i < p.size(); i++) p[i].dist += p[i - 1].dist; //预处理距离的前缀和}for(int i = h[u]; i != -1; i = ne[i]) calc(e[i]); //递归构建每棵子树
}LL query(int u, int l, int r) //计算所有年龄在 [l, r] 之间的点到 u 的距离之和
{LL res = 0; //记录答案for(int i = 0; i < f[u].size(); i++) //枚举 u 所在的每一层{auto &t = f[u][i]; //记录当前层的重心int g = age[t.u];if(g >= l && g <= r) res += t.dist; //如果重心也在年龄范围内，单独考虑for(int j = 0; j < 3; j++) //枚举重心的所有子树{if(j == t.num) continue; //和 u 在同一棵子树的节点不用考虑auto &p = son[t.u][j]; //当前子树的所有节点if(p.empty()) continue; //如果当前子树为空，直接跳过int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin() - 1;res += t.dist * (b - a + 1) + p[b].dist - p[a - 1].dist; //计算当前层和 u 不在同一子树的所有路径的距离和}}for(int i = 0; i < 3; i++) //枚举 u 的所有子树{auto &p = son[u][i]; //当前子树的所有节点if(p.empty()) continue; //如果当前子树为空，直接跳过int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin() - 1;res += p[b].dist - p[a - 1].dist; //计算当前子树中所有路径的距离和}return res;
}int main()
{scanf("%d%d%d", &n, &m, &A);for(int i = 1; i <= n; i++) scanf("%d", &age[i]);memset(h, -1, sizeof h); //初始化邻接表for(int i = 0; i < n - 1; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c); //无向边}calc(1); //构建点分树LL res = 0; //记录当前的答案while(m--){int u, a, b;scanf("%d%d%d", &u, &a, &b);int l = (a + res) % A, r = (b + res) % A;if(l > r) swap(l, r);res = query(u, l, r); //查询当前询问printf("%lld\n", res);}return 0;
}