[POI2015]Odwiedziny

发布于 2020-08-06  24 次阅读



这题实际上比较套路......
注意到 $n\le 50000$,大概率是想让我们用个 $\mathcal{O}(n\sqrt{n})$ 的复杂度。想到根号复杂度的话就很有可能是个根号分治。这题也不例外。
我们按照 $k$ 的大小分成两类:假设一个界为 $B=200$,当 $k\ge B$ 的时候就可以直接暴力模拟这个跳的过程,当 $k<B$ 的时候就可以考虑用什么东西来维护。
先说简单的部分:暴力向上跳。我们可以将路径 $x\to y$ 拆成 $x\to lca,lca \to y$。这样的话,我们需要距离 $x$ 为 $k$ 的祖先是哪一个(也就是 $x$ 的 $k$ 级祖先)。这一部分我们可以用长链剖分来搞,虽然慢了点但还是能过。这样的话,就可以将路径看成 $x$ 到 $lca$,$y$ 到 $lca$。
注意一个细节:$y$ 需要先往上跳一小段再暴力跳到 $lca$,因为题目中有说 “距离小于 $k$ 的话就直接一步跳到 $y$”。这样的话,因为 $y$ 往上跳与实际路径方向相反,所以需要先处理这一小段。
之后再说 $k<B$ 的部分。设 $s(i,j)$ 表示从 $i$ 开始每次跳 $j$ 步一直跳到根节点为止的路径上的点权和(当然也有可能跳不到根节点,但这个其实无所谓,因为这个时候再跳 $j$ 步的话已经跳出去了)。这一步有一个递推式子:设 $f(i,j)$ 表示 $i$ 的 $j$ 级祖先是哪个点,那么显然我们就有 $s(i,j)=s(f(i,j),j)+a_i$($a_i$ 为点权),注意 $f(i,j)$ 可能不存在,这个时候就是 $s(i,j)=a_i$。
之后,我们可以算出 $s(x,k)$ 并减去在 $lca(x,y)$ 上方的部分贡献,同理也可以算出 $s(y,k)$ 并减去在 $lca(x,y)$ 上方的部分贡献。
综上,这个题就做完了。
但是这题细节是真的超多......

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 50050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
const int M = 201;
int s[N][M], a[N];
int n;
int b[N], d[N], f[N][16], son[N], dep[N], top[N], g[N];
vector<int> e[N], u[N], v[N];
void dfs(int x, int fa)
{
    dep[x] = d[x] = d[fa] + 1;
    f[x][0] = fa;
    for (int i = 1; (1 << i) <= d[x]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (auto y : e[x])
    {
        if (y == fa)
            continue;
        dfs(y, x);
        if (dep[y] > dep[x])
            dep[x] = dep[y], son[x] = y;
    }
}
inline int getlca(int a, int b)
{
    if (d[a] > d[b])
        swap(a, b);
    for (int i = 15; i >= 0; i--)
        if (d[a] <= d[b] - (1 << i))
            b = f[b][i];
    if (a == b)
        return a;
    for (int i = 15; i >= 0; i--)
    {
        if (f[a][i] == f[b][i])
            continue;
        else
            a = f[a][i], b = f[b][i];
    }
    return f[a][0];
}
inline int getdis(int x, int y) { return d[x] + d[y] - 2 * d[getlca(x, y)]; }
void dfs(int x, int p, int fa)
{
    top[x] = p;
    if (x == p)
    {
        for (int i = 0, o = x; i <= dep[x] - d[x]; ++i)
            u[x].pb(o), o = f[o][0];
        for (int i = 0, o = x; i <= dep[x] - d[x]; ++i)
            v[x].pb(o), o = son[o];
    }
    if (son[x])
        dfs(son[x], p, f[son[x]][0]);
    for (auto y : e[x])
        if (y != son[x] && y != fa)
            dfs(y, y, x);
}
inline int ask(int x, int k)
{
    if (!k)
        return x;
    x = f[x][g[k]], k -= 1 << g[k], k -= d[x] - d[top[x]], x = top[x];
    return k >= 0 ? (k < (int)u[x].size() ? u[x][k] : -1) : (k < (int)v[x].size() ? v[x][-k] : -1);
}
void dfs2(int x, int fa)
{
    for (int j = 1; j < M; ++j)
    {
        if (ask(x, j) == -1)
            s[x][j] = a[x];
        else
            s[x][j] = s[ask(x, j)][j] + a[x];
    }
    for (auto vv : e[x])
    {
        if (vv == fa)
            continue;
        dfs2(vv, x);
    }
}
inline int queryBig(int x, int y, int k)
{
    int resx = 0, resy = 0;
    int lca = getlca(x, y), D = getdis(x, y);
    int dx = getdis(x, lca), dy = getdis(y, lca);
    if (lca == x)
    {
        int ry = D
        if (ry)
            resy += a[y];
        y = ask(y, ry);
        while (~y && d[y] >= d[lca])
            resy += a[y], y = ask(y, k);
        return resy;
    }
    while (~x && d[x] > d[lca])
        resx += a[x], x = ask(x, k);
    if (lca == y)
        return resx + a[y];
    int ry = D
    if (ry)
        resy += a[y];
    y = ask(y, ry);
    while (~y && d[y] > d[lca])
        resy += a[y], y = ask(y, k);
    if (dx
        resx += a[lca];
    return resx + resy;
}
inline int querySmall(int x, int y, int k)
{
    int resx = 0, resy = 0;
    int lca = getlca(x, y), D = getdis(x, y);
    int ry = D
    if (ry)
        resy += a[y];
    if (lca == x)
    {
        y = ask(y, ry);
        int lcay = ask(lca, k);
        resy += (y == -1 ? 0 : s[y][k]) - (lcay == -1 ? 0 : s[lcay][k]);
        return resy;
    }
    if (lca == y)
    {
        int lcax = ask(lca, k - D
        resx += s[x][k] - (lcax == -1 ? 0 : s[lcax][k]);
        return resx;
    }
    int dx = getdis(x, lca);
    int lcax = ask(lca, k - dx
    resx += s[x][k] - (lcax == -1 ? 0 : s[lcax][k]);
    y = ask(y, ry);
    int lcay = ask(lca, dx
    resy += (y == -1 ? 0 : s[y][k]) - (lcay == -1 ? 0 : s[lcay][k]);
    return resx + resy;
}
inline void solve()
{
    scanf(
    g[0] = -1;
    for (int i = 1; i <= n; ++i)
        g[i] = g[i >> 1] + 1, scanf(
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        scanf(
        e[x].push_back(y), e[y].push_back(x);
    }
    dfs(1, 0);
    dfs(1, 1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; ++i)
        scanf(
    int uu, vv, k;
    for (int i = 2; i <= n; ++i)
    {
        scanf(
        int ans = 0;
        if (k >= M)
            ans = queryBig(b[i - 1], b[i], k);
        else
            ans = querySmall(b[i - 1], b[i], k);
        printf(
    }
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}