暑假集训系列题解（八）
题目1
题目链接
题目描述
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures. Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures. Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads. He will do so using a procedure consisting of M steps (1 <= M <=100,000).
At each step one of two things will happen:
- FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,
- Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.
Farmer John is a very poor counter -- help him answer Bessie's questions!
输入
- Line 1: Two space-separated integers N and M
- Lines 2..N: Two space-separated integers describing the endpoints of
a road. Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A_i and B_i (1 <= A_i, B_i <= N) which describe FJ's action or query.
输出
- Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.
样例输入
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4样例输出
2
1
2题解
树链剖分，将树进行边剖分利用线段树维护即可。
参考链接：
https://oi-wiki.org/graph/hld/#_4
代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[400500] = {0}, lazy[400500] = {0};
ll dep[200500] = {0}, size1[200500] = {0}, son[200500] = {0}, f[200500] = {0}, id[200500] = {0}, top[200500] = {0};
struct node
{
ll to, next;
};
node edge[400500] = {0};
ll head[400500] = {0};
ll num = 0, cnt = 0;
void add_edge(ll from, ll to)
{
edge[++num] = {to, head[from]};
head[from] = num;
}
void dfs1(ll now, ll fa)
{
size1[now] = 1;
for (ll i = head[now]; i; i = edge[i].next)
{
ll to = edge[i].to;
if (to == fa)
continue;
f[to] = now;
dep[to] = dep[now] + 1;
dfs1(to, now);
size1[now] += size1[to];
if (size1[to] > size1[son[now]])
son[now] = to;
}
}
void dfs2(ll now, ll fa)
{
id[now] = ++cnt;
top[now] = fa;
if (son[now])
dfs2(son[now], fa);
for (ll i = head[now]; i; i = edge[i].next)
{
ll to = edge[i].to;
if (to == f[now] || to == son[now])
continue;
dfs2(to, to);
}
}
void push_down(ll t, ll l, ll r)
{
if (lazy[t] == 0)
return;
lazy[2 * t + 1] += lazy[t];
lazy[2 * t] += lazy[t];
ll mid = (l + r) / 2;
sum[2 * t] += (mid - l + 1) * lazy[t];
sum[2 * t + 1] += (r - mid) * lazy[t];
lazy[t] = 0;
}
void push_up(ll t)
{
sum[t] = sum[2 * t] + sum[2 * t + 1];
}
void update(ll t, ll l, ll r, ll L, ll R, ll add)
{
if (l <= L && R <= r)
{
lazy[t] += add;
sum[t] += add * (R - L + 1);
return;
}
push_down(t, L, R);
ll mid = (L + R) / 2;
if (l <= mid)
update(2 * t, l, r, L, mid, add);
if (mid < r)
update(2 * t + 1, l, r, mid + 1, R, add);
push_up(t);
}
ll query(ll t, ll l, ll r, ll L, ll R)
{
if (l <= L && R <= r)
return sum[t];
push_down(t, L, R);
ll mid = (L + R) / 2;
ll ans = 0;
if (l <= mid)
ans += query(2 * t, l, r, L, mid);
if (mid < r)
ans += query(2 * t + 1, l, r, mid + 1, R);
return ans;
}
void update_chain(ll x, ll y)
{
ll fx = top[x], fy = top[y];
while (fx != fy) ///不在同一条重链上
{
if (dep[fx] < dep[fy])
swap(x, y), swap(fx, fy);
update(1, id[fx], id[x], 1, cnt, 1);
x = f[fx], fx = top[x]; ///跳转到另一条重链
}
if (id[x] > id[y])
swap(x, y);
update(1, id[x] + 1, id[y], 1, cnt, 1);
}
ll query_chain(ll x, ll y)
{
ll fx = top[x], fy = top[y], ans = 0;
while (fx != fy) ///不在同一条重链上
{
if (dep[fx] < dep[fy])
swap(x, y), swap(fx, fy);
ans += query(1, id[fx], id[x], 1, cnt);
x = f[fx], fx = top[x]; ///跳转到另一条重链
}
if (id[x] > id[y])
swap(x, y);
ans += query(1, id[x] + 1, id[y], 1, cnt);
return ans;
}
int main()
{
ll n, m, from, to;
scanf("%lld%lld", &n, &m);
for (ll i = 1; i <= n - 1; i++)
{
scanf("%lld%lld", &from, &to);
add_edge(from, to);
add_edge(to, from);
}
f[1] = 0, dep[1] = 1;
dfs1(1, 0), dfs2(1, 1);
char c[10];
for (ll i = 1; i <= m; i++)
{
scanf("%s%lld%lld", c + 1, &from, &to);
if (c[1] == 'P')
update_chain(from, to);
else
printf("%lld\n", query_chain(from, to));
}
}