模板题,难点在于怎样将点权变为边权。
我们可以考虑这样的事情,对于树上除了根之外的所有点,都有入边仅为 \(1\), 出边可能为多条 则我们可以将这条入边的边权转化到这个点上。
树链剖分之后得到区间,我们可以知道对于树询问路径最后一段询问中 \(u,v\) 所在的重链为同一条,所以在转化后这段区间是连续的,我们只需要把这棵子树的根节点去掉即可, 即 \((id[v] + 1, id[u])\)。
\(Code\)
#include <bits/stdc++.h>
#define L u << 1
#define R u << 1 | 1
using namespace std;
const int maxn = 100010, maxm = maxn * 2;
int n, m;
int h[maxn], e[maxm], ne[maxm], idx;
int dep[maxn], fa[maxn], sz[maxn], son[maxn];
int id[maxn], top[maxn], cnt;
struct Node
{
int l, r;
int sum, add;
}tr[maxn << 2];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1(int u, int father, int depth)
{
dep[u] = depth, fa[u] = father, sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[j] > sz[son[u]]) son[u] = j;
}
}
void dfs2(int u, int t)
{
id[u] = ++ cnt, top[u] = t;
if (!son[u]) return;
dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}
void pushup(int u)
{
tr[u].sum = tr[L].sum + tr[R].sum;
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[L], &right = tr[R];
if (root.add)
{
left.add += root.add, left.sum += (left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
tr[u] = {l, r, 0, 0};
if (l == r) return;
int mid = l + r >> 1;
build(L, l, mid), build(R, mid + 1, r);
pushup(u);
}
void update(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += tr[u].r - tr[u].l + 1;
tr[u].add ++ ;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(L, l, r);
if (r > mid) update(R, l, r);
pushup(u);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res += query(L, l, r);
if (r > mid) res += query(R, l, r);
return res;
}
void update_path(int u, int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
update(1, id[v] + 1, id[u]);
}
int query_path(int u, int v)
{
int res = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res += query(1, id[v] + 1, id[u]);
return res;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (*op == 'P') update_path(a, b);
else printf("%d\n", query_path(a, b));
}
return 0;
}
原文地址:http://www.cnblogs.com/mrCrazyWolf/p/16928392.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性