求树上长度小于等于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 - 1
res += 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; //重置 f
for(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); //初始化 f
calc(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;
}