专栏文章

题解：P9808 [POI 2022 ~2023R1] zbo

aa_small_penguin
P9808题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipbe7nv
此快照首次捕获于
2025/12/03 09:14
3 个月前
此快照最后确认于
2025/12/03 09:14
3 个月前
查看原文
这是蒟蒻的第一篇紫题题解。
暴力拆解即可。
定义 ii 为已修建城堡个数，ansans 是需要吃掉的谷子。
接下来开始拆式子！
ans=∑x=1i∑y=1idis(x,y)⁡=∑x=1i∑y=1idis(x,1)⁡+dis(y,1)⁡−2dis(lca(x,y)⁡,1)⁡=∑x=1i∑y=1idis(x,1)⁡+∑x=1i∑y=1idis(y,1)⁡−2∑x=1i∑y=1idis(lca(x,y)⁡,1)⁡=2i∑x=1idis(1,x)⁡−2∑x=1i∑y=1idis(lca(x,y),1⁡)⁡=2i∑x=1idis(1,x)⁡−4∑x=1i∑y=x+1idis(lca(x,y),1⁡)⁡−2∑x=1idis(1,x)⁡=2(i−1)∑x=1idis(1,x)⁡−4∑x=1i∑y=x+1idis(lca(x,y),1⁡)⁡\begin{aligned} ans &= \sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(x,y)} \\ &= \sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(x,1)} + \operatorname{dis(y,1)} - 2 \operatorname{dis(\operatorname{lca{(x,y)}},1)} \\ &= \sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(x,1)} + \sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(y,1)} - 2 \sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(\operatorname{lca{(x,y)}},1)} \\ &= 2i\sum^{i}_{x = 1} \operatorname{{dis(1, x)}} - 2\sum^{i}_{x = 1} \sum^{i}_{y = 1} \operatorname{dis(\operatorname{{lca(x,y)},1})} \\ &= 2i\sum^{i}_{x = 1} \operatorname{{dis(1, x)}} - 4\sum^{i}_{x = 1} \sum^{i}_{y = x + 1} \operatorname{dis(\operatorname{{lca(x,y)},1})} - 2\sum^{i}_{x = 1} \operatorname{dis(1, x)} \\ &= 2(i-1)\sum^{i}_{x = 1} \operatorname{{dis(1, x)}} - 4\sum^{i}_{x = 1} \sum^{i}_{y = x + 1} \operatorname{dis(\operatorname{{lca(x,y)},1})} \end{aligned}
令a=∑x=1idis(1,x)⁡,b=∑x=1i∑y=x+1idis(lca(x,y),1⁡)⁡\text{令} a = \sum^{i}_{x = 1} \operatorname{{dis(1, x)}},b= \sum^{i}_{x = 1} \sum^{i}_{y = x + 1} \operatorname{dis(\operatorname{{lca(x,y)},1})}
那么，ans=2a(i−1)−4bans = 2a(i-1) - 4b，对于多出的城堡 aa 直接计算。bb 用类似 P4211 LCA 的思路进行维护。
唯四区别是：
  • 加的不是点权，而是点权的常数。
  • 查询是查询常数 ×\times 点权。
  • 线段树还要维护一个点权和。
  • 改变 a,ba,b，再对于 1→x1 \to x 的路径进行加常数。
code：
CPP
#include <bits/stdc++.h>
using namespace std;

#define N 100009
#define int long long
#define ls(i) (i << 1)
#define rs(i) ((i << 1) | 1)
#define sp(i, j) i ^= j, j ^= i, i ^= j
#define mod 0x7fffffffffffffff
#define qj(i, x) tree[i].d += x * tree[i].a, tree[i].lazy += x
#define pd(i) qj(ls(i), tree[i].lazy), qj(rs(i), tree[i].lazy), tree[i].lazy = 0
struct V
{
    vector<int> e;
    int size, top, h, d, id, fa, son;
} v[N];
int rk[N], n, m, res, r;
namespace xds
{
    struct TREE
    {
        int d, lazy, l, r, a;
    } tree[(N << 2)];
    void build(int i, int l, int r)
    {
        tree[i].l = l, tree[i].r = r;
        if (l == r)
        {
            tree[i].a = v[rk[l]].d;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(i), l, mid), build(rs(i), mid + 1, r), tree[i].a = tree[ls(i)].a + tree[rs(i)].a;
    }
    int ask(int i, int l, int r)
    {
        if (l <= tree[i].l && tree[i].r <= r)
            return tree[i].d;
        if (tree[i].lazy)
            pd(i);
        int d = 0, mid = (tree[i].l + tree[i].r) >> 1;
        if (l <= mid)
            d += ask(ls(i), l, r);
        if (mid < r)
            d += ask(rs(i), l, r);
        return d;
    }
    int dis(int i, int l, int r)
    {
        if (l <= tree[i].l && tree[i].r <= r)
            return tree[i].a;
        int d = 0, mid = (tree[i].l + tree[i].r) >> 1;
        if (l <= mid)
            d += dis(ls(i), l, r);
        if (mid < r)
            d += dis(rs(i), l, r);
        return d;
    }
    void add(int i, int l, int r, int k)
    {
        if (tree[i].r <= r && tree[i].l >= l)
        {
            qj(i, k);
            return;
        }
        if (tree[i].lazy)
            pd(i);
        if (tree[ls(i)].r >= l)
            add(ls(i), l, r, k);
        if (tree[rs(i)].l <= r)
            add(rs(i), l, r, k);
        tree[i].d = tree[ls(i)].d + tree[rs(i)].d;
    }
}
void dfs(int u, int fa, int h)
{
    v[u].h = h, v[u].fa = fa, v[u].size = 1;
    int cnt = -114514;
    for (auto to : v[u].e)
    {
        if (to == fa)
            continue;
        dfs(to, u, h + 1);
        v[u].size += v[to].size;
        if (cnt < v[to].size)
            v[u].son = to, cnt = v[to].size;
    }
}
void dfs2(int u, int top)
{
    v[u].top = top, v[u].id = ++res, rk[res] = u;
    if (!v[u].son)
        return;
    dfs2(v[u].son, top);
    for (auto to : v[u].e)
        if ((to ^ v[u].son) && (to ^ v[u].fa))
            dfs2(to, to);
}
void add(int x, int y)
{
    while (v[x].top ^ v[y].top)
    {
        if (v[v[x].top].h < v[v[y].top].h)
            sp(x, y);
        xds::add(1, v[v[x].top].id, v[x].id, 1), x = v[v[x].top].fa;
    }
    if (v[x].id > v[y].id)
        sp(x, y);
    xds::add(1, v[x].id, v[y].id, 1);
}
int ask(int x, int y)
{
    int ans = 0;
    while (v[x].top ^ v[y].top)
    {
        if (v[v[x].top].h < v[v[y].top].h)
            sp(x, y);
        ans += xds::ask(1, v[v[x].top].id, v[x].id), ans, x = v[v[x].top].fa;
    }
    if (v[x].id > v[y].id)
        sp(x, y);
    ans += xds::ask(1, v[x].id, v[y].id);
    return ans;
}
int dis(int x, int y)
{
    int ans = 0;
    while (v[x].top ^ v[y].top)
    {
        if (v[v[x].top].h < v[v[y].top].h)
            sp(x, y);
        ans += xds::dis(1, v[v[x].top].id, v[x].id), ans, x = v[v[x].top].fa;
    }
    if (v[x].id > v[y].id)
        sp(x, y);
    ans += xds::dis(1, v[x].id, v[y].id);
    return ans;
}

int _u[N];
int _v[N];
int _w[N];
int A, B;

signed main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        cin >> _u[i] >> _v[i] >> _w[i];
        v[_u[i]].e.push_back(_v[i]);
        v[_v[i]].e.push_back(_u[i]);
    }
    dfs(1, 0, 1);
    dfs2(1, 1);
    for (int i = 1; i < n; i++)
    {
        if (v[_u[i]].h > v[_v[i]].h)
            sp(_u[i], _v[i]);
        v[_v[i]].d = _w[i];
    }
    xds::build(1, 1, n);
    add(1, 1);
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        A += dis(1, x);
        B += ask(1, x);
        cout << 2 * i * A - 4 * B << "\n";
        add(1, x);
    }

    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...