不动笔只是对着屏幕发呆是想不出解法的

不过…据说…晴天会让人心情好一些哦qwq

但是我为什么活的这么痛苦呢…

懵逼的 题目

qwq

扯淡的 题解

没什么用的思路

思路还是挺简单的…然而….

我们具体需要些啥呢…

  • 一个函数int qwq(LL x), 返回输入中的x所在的新节点的编号, 这个可以利用 前缀和×二分 搞一下
  • 一个函数int qwqwq(LL x), 返回输入的x在模板树中的编号, 这个可以…
    • 用一个数组rb[i]来记录第i个新节点包含的树(在模板树中)的树根
    • 建一棵主席树, int cx(int dq, int pre, int k)能够查询dfs序上一棵子树($[pre, dq]$)的第k大
    • 返回cx(root[ta[rb[qwq(x)]].end], root[ta[rb[qwq(x)]].begin - 1], x - fr_size[qwq(x)]);
  • 一个函数int lca(int x, int y), 返回在模板树中这两个点x, y的距离
  • 一个函数LL qwqlca(LL x, LL y), 返回在新树中这两个节点的距离
    • 一个数组cmt[x], 来记录x(新节点)通过(模板树中的)cmt[x]到达他的父亲, 也就是题目中的b1
    • 一个函数通过倍增求$LCA(x, y)$, 有三种情况
      1. $x, y$在一个新节点中: 直接找到他们在模板树中的编号, 然后返回其$LCA$即可
      2. $y$是$x$的祖先, 也就是没跳到深度相等, 就发现d[x][0] == y了: 返回cost + lca(cmt[x], qwqwq(y))(cost为已经跳过的距离)
      3. $x, y$在$LCA_{x, y}$不同的子树中: 返回cost + lca(cmt[x], cmt[y])

好像也就是这么点东西是不…

这里写图片描述

沙茶的 代码

好恶心…

  • 写主席树的时候…把左右边界写错了…居然还没看出来…

  • 不要忘记在加边权的时候, 新节点父亲的根不一定是模板树的根, 还要减一遍他真正根的深度

/**************************************************************
    Problem: 4539
    User: Cansult
    Language: C++
    Result: Accepted
    Time:20968 ms
    Memory:125292 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXL (20 + 5)
#define pll pair<LL, LL>
#define LL long long
#define int LL
using namespace std;
struct edg
{
    int from, to, next, cost;
};
struct hnode
{
    int ls, rs, zh;
    hnode(): ls(0), rs(0), zh(0) {}
};
struct tnode
{
    int size, begin, end;
};
struct htree
{
    hnode b[MAXN * 20];
    int root[MAXN], cnt;
    htree(): cnt(0) { memset(root, 0, sizeof(root)); }
    void xg(int, int&, int, int, int);
    int cx(int, int, int, int, int);
} hjt;
struct tree
{
    edg b[MAXN << 1];
    tnode ta[MAXN]; // 记录一个节点的子树
    int n, lgn, d[MAXN][MAXL], deep[MAXN], g[MAXN], cntb, a[MAXN], cnta;
    LL cost[MAXN];
    tree(): cntb(-1), cnta(0) { memset(g, -1, sizeof(g)); }
    int lg(int);
    void dfs(int, int);
    int lca(int, int); // 返回在模板树中这两个点x, y的距离
    int tlca(int, int); // 返回两个点的lca
    void adn(int, int, int);
} qwqo, qwqn; // 模板树, 新树
int n, m, cmt[MAXN], rb[MAXN]; // cmt[]: 来记录x(新节点)通过(模板树中的)cmt[x]到达他的父亲, 也就是题目中的b; rb[]: 来记录第i个新节点包含的树(在模板树中)的树根
LL fr_size[MAXN];
pll QAQsra[MAXN];
int qwq(LL); // 返回输入中的x所在的新节点的编号
int qwqwq(LL); // 返回输入的x在模板树中的编号
LL qwqlca(LL, LL); // 返回在新树中这两个节点的距离
main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
#endif // ONLINE_JUDGE
    int q;
    scanf("%lld%lld%lld", &n, &m, &q);
    qwqo.n = n, qwqn.n = ++m;
    for (int i = 1, srx, sry; i < n; i++)
        scanf("%lld%lld", &srx, &sry), qwqo.adn(srx, sry, 1), qwqo.adn(sry, srx, 1);
    qwqo.d[1][0] = 1, qwqo.lgn = qwqo.lg(qwqo.n), qwqo.cost[1] = 0;
    qwqo.dfs(1, 0);
    for (int i = 1; i <= n; i++)
        hjt.xg(hjt.root[i - 1], hjt.root[i], 1, n, qwqo.a[i]);
    fr_size[1] = n, rb[1] = 1, cmt[1] = 1;
    for (int i = 2; i <= m; i++)
        scanf("%lld%lld", &QAQsra[i].first, &QAQsra[i].second),
        fr_size[i] = fr_size[i - 1] + qwqo.ta[QAQsra[i].first].size;
    for (int i = 2; i <= m; i++)
    {
        LL sra = QAQsra[i].first, srb = QAQsra[i].second;
        int tb = qwqwq(srb), nb = qwq(srb), nc = qwqo.deep[tb] - qwqo.deep[rb[nb]] + 1; // 就是这个地方, 忘记减去qwqo.deep[rb[nb]]了
        cmt[i] = tb, rb[i] = sra;
        qwqn.adn(i, nb, nc); // 这里的cost其实是当前复制的根到他父亲的根的距离
        qwqn.adn(nb, i, nc);
    }
    qwqn.d[1][0] = 1, qwqn.lgn = qwqn.lg(qwqn.n), qwqn.cost[1] = 0;
    qwqn.dfs(1, 0);
    for (int i = 1; i <= q; i++)
    {
        LL srx, sry;
        scanf("%lld%lld", &srx, &sry);
        printf("%lld\n", qwqlca(srx, sry));
    }
    return 0;
}
int qwq(LL x) // 返回输入中的x所在的新节点的编号
{
    return lower_bound(fr_size + 1, fr_size + m + 1, x) - fr_size;
}
int qwqwq(LL x) // 返回输入的x在模板树中的编号
{
    int bln = qwq(x), belong = rb[bln];
    return hjt.cx(hjt.root[qwqo.ta[belong].begin - 1], hjt.root[qwqo.ta[belong].end], 1, qwqo.n, x - fr_size[bln - 1]);
}
int tree::lca(int x, int y) // 返回在模板树中这两个点x, y的距离
{
    int re = cost[x] + cost[y];
    return (re - (cost[tlca(x, y)] << 1));
}
LL qwqlca(LL bx, LL by) // 返回在新树中这两个节点的距离
{
    int x = qwq(bx), y = qwq(by), lca = qwqn.tlca(x, y);
    if (x == y)
        return qwqo.lca(qwqwq(bx), qwqwq(by));
    LL re = qwqn.cost[x] + qwqn.cost[y] - (qwqn.cost[lca] << 1);
    re += qwqo.deep[qwqwq(by)] - qwqo.deep[rb[y]];
    re += qwqo.deep[qwqwq(bx)] - qwqo.deep[rb[x]];
    if (qwqn.deep[x] < qwqn.deep[y])
        swap(x, y), swap(bx, by);
    if (lca == y)
    {
        for (int i = qwqn.lgn; i >= 0; i--)
            if (qwqn.deep[qwqn.d[x][i]] > qwqn.deep[y])
                x = qwqn.d[x][i];
        int olca = qwqo.tlca(cmt[x], qwqwq(by));
        re -= (qwqo.deep[olca] - qwqo.deep[rb[lca]]) << 1;
        return re;
    }
    else
    {
        for (int i = qwqn.lgn; i >= 0; i--)
            if (qwqn.deep[qwqn.d[x][i]] >= qwqn.deep[y])
                x = qwqn.d[x][i];
        for (int i = qwqn.lgn; i >= 0; i--)
            if (qwqn.d[x][i] != qwqn.d[y][i])
                x = qwqn.d[x][i], y = qwqn.d[y][i];
        int olca = qwqo.tlca(cmt[x], cmt[y]);
        re -= (qwqo.deep[olca] - qwqo.deep[rb[lca]]) << 1;
        return re;
    }
}
void htree::xg(int pre, int& dq, int le, int ri, int zh)
{
    dq = ++cnt;
    if (le == ri)
    {
        b[dq].zh = b[pre].zh + 1;
        return ;
    }
    int mi = (le + ri) >> 1;
    if (zh > mi)
        b[dq].ls = b[pre].ls, xg(b[pre].rs, b[dq].rs, mi + 1, ri, zh); // 这个地方...ri写成le了...
    else
        b[dq].rs = b[pre].rs, xg(b[pre].ls, b[dq].ls, le, mi, zh);
    b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh;
}
int htree::cx(int pre, int dq, int le, int ri, int k)
{
    if (le == ri)
        return le;
    int mi = (le + ri) >> 1, ka = b[b[dq].ls].zh - b[b[pre].ls].zh;
    if (k <= ka)
        return cx(b[pre].ls, b[dq].ls, le, mi, k);
    else
        return cx(b[pre].rs, b[dq].rs, mi + 1, ri, k - ka);
}
void tree::adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
int tree::lg(int x)
{
    int re = 0;
    while ((1 << re) <= x)
        ++re;
    return re + 1;
}
void tree::dfs(int dq, int de)
{
    deep[dq] = de;
    a[ta[dq].begin = ++cnta] = dq;
    ta[dq].size = 1;
    for (int i = 1; i <= lgn; i++)
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = g[dq]; ~i; i = b[i].next)
        if (b[i].to != d[dq][0])
        {
            d[b[i].to][0] = dq, cost[b[i].to] = cost[dq] + b[i].cost;
            dfs(b[i].to, de + 1);
            ta[dq].size += ta[b[i].to].size;
        }
    ta[dq].end = cnta;
}
int tree::tlca(int x, int y)
{
    if (deep[x] < deep[y])
        swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            x = d[x][i];
    if (x == y)
        return x;
    for (int i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            x = d[x][i], y = d[y][i];
    return d[x][0];
}

/*
10 2 6
1 2
1 3
2 10
3 4
3 5
4 6
4 7
7 8
7 9

4 10
2 5

15 12
15 11
15 5
16 5
15 17
11 17

5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3
*/

REfun妹子成群! REfun吊打学长!

By Cansult


  1. 1.(2.2)将模板树中以结点a为根的子树复制一遍,挂到大树中结点b的下方(也就是说,模板树中的结点a为根的子树复制到大树中后,将成为大树中结点b的子树