Children Trips
题意：给定一棵树n个点，边权为1或2。有m个询问，每次给出u，v，p。表示要从点u到点v，每天只能至多p的长度，且只能在节点处停留。对于每个询问，求至少需要几天。
主要方法：对于这种指定方向跳的题目，在序列上有分块的做法，在树上也可以用。可以发现每次的只询问一条路径。所以选择限制直径、限制个数、不限制大小的树分块。
1、对于(p>sqrt{n})的情况，可以证明暴力跳的话不会超过(O(sqrt{n}))次。
2、对于(p<sqrt{n})的情况，可以预处理每个点每种p的答案。然后每次一块一块跳，由于限制了个数，所以也是(O(sqrt{n}))的。
其实，说实话，写起来是真滴烦。
考虑一个询问u，v，p。令lca(u,v)=l。可以证明从u到l每天跳最多+从v到l每天跳最多=直接从u到v每天条最多=答案。需要注意的是，u到l最后一天剩下距离x，v到l最后一天剩下距离y，如果(x+y>=p)那么答案可以减少1。
#include <bits/stdc++.h>
using namespace std;
int n, w, fa[100005], d[100005], m, key[100005], p, fly[100005][680], stp[100005][680], lef[100005][680];
vector<pair<int, int> > G[100005];
int dfs1(int u, int dep) {
int siz = 1;
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first;
if (v == fa[u])
continue;
d[v] = d[u] + G[u][i].second;
fa[v] = u;
siz += dfs1(v, dep + 1);
}
if (dep % w == 1 && (u == 1 || siz >= w)) {
key[u] = u;
siz = 0;
}
return siz;
}
void dfs2(int u) {
if (!key[u])
key[u] = key[fa[u]];
fly[u][0] = u;
for (int i = 1; i <= w + w; ++i) {
fly[u][i] = fly[u][i - 1];
if (fly[u][i] != key[u] && d[u] - d[fa[fly[u][i]]] <= i)
fly[u][i] = fa[fly[u][i]];
if (fly[u][i] == key[u]) {
stp[u][i] = 1;
lef[u][i] = i - (d[u] - d[key[u]]);
} else {
stp[u][i] = stp[fly[u][i]][i] + 1;
lef[u][i] = lef[fly[u][i]][i];
}
}
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i].first;
if (v == fa[u])
continue;
dfs2(v);
}
}
int LCA(int u, int v) {
while (key[u] != key[v]) {
if (d[key[u]] < d[key[v]])
swap(u, v);
u = fa[key[u]];
}
while (u != v) {
if (d[u] < d[v])
swap(u, v);
u = fa[u];
}
return u;
}
int work(int u, int e, int &s) {
if (u == e)
return 0;
int LEF = 0;
if (p > 2 * w) {
while (key[u] != key[e]) {
if (d[u] - d[fa[key[u]]] <= LEF)
LEF -= d[u] - d[fa[key[u]]];
else {
++s;
LEF = p - d[fly[u][LEF]] + d[fa[key[u]]];
}
u = fa[key[u]];
}
} else {
while (key[u] != key[e]) {
if (d[u] - d[fa[key[u]]] <= LEF)
LEF -= d[u] - d[fa[key[u]]];
else {
u = fly[u][LEF];
s += stp[u][p];
LEF = lef[u][p];
if (d[key[u]] - d[fa[key[u]]] <= LEF)
LEF -= d[key[u]] - d[fa[key[u]]];
else {
++s;
LEF = p - d[key[u]] + d[fa[key[u]]];
}
}
u = fa[key[u]];
}
}
while (u != e) {
if (d[u] - d[fa[u]] <= LEF)
LEF -= d[u] - d[fa[u]];
else {
++s;
LEF = p - d[u] + d[fa[u]];
}
u = fa[u];
}
return LEF;
}
int main() {
scanf("%d", &n);
w = sqrt(n);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
dfs1(1, 1);
dfs2(1);
scanf("%d", &m);
while (m--) {
int u, v;
scanf("%d%d%d", &u, &v, &p);
int lca = LCA(u, v), s1 = 0, s2 = 0;
int l1 = work(u, lca, s1);
int l2 = work(v, lca, s2);
printf("%d
", s1 + s2 - (l1 + l2 >= p));
}
return 0;
}
```