P4216 [SCOI2015] 情报传递题解

来一篇常数不大的最优解题解。

Link

Solution

对于每个询问，第一问是基础的树上问题，公式放在下面，不在赘述。

\[\operatorname{dis}\left(u,v\right) = dep_{u} + dep_{v} - 2 \times dep_{\operatorname{lca}\left(u,v\right)} + 1 \]

首先，我们可以转化一下题意：题目求某条链上危险程度大于 \(C\) 的节点数，而一个节点的危险程度又只与开始时间和查询时间有关，对于每个询问，查询时间是一定的，因此对于第 \(i\) 个询问，我们查询的就是 \(X_{i} \rArr Y_{i}\) 这条链上开始搜集情报时间在 \(i - C_{i}\) 之前的节点数。

每次清空重新查询复杂度是 \(\Omicron \left(n^{2} \log^{2}n\right)\) 的。

考虑离线，由于只查询在 \(i - C_{i}\) 之前的点，因此我们可以将查询按照 \(i - C_{i}\) 排序。查询时我们先加入满足开始搜集情报时间在 \(i - C_{i}\) 之前的新点。

利用树链剖分，我们可以把 \(X_{i} \rArr Y_{i}\) 的路径拆分成若干 dfs 序连续的短链，我们可以利用树状数组查询这些短链上符合要求的点数。

时间复杂度 \(\Omicron \left( n \log^2{n} \right)\)，树状数组常数小，跑的飞快。

Codes

#include <bits/stdc++.h>
using namespace std;
#define max_n 200001
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
struct node
{
    int to,nxt;
}edge[max_n];
int head[max_n],tot;
void add(int u,int v)
{
    edge[++tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
int n,q,root;
int fa[max_n],siz[max_n],dfn[max_n],rev[max_n],dep[max_n],son[max_n],top[max_n],timer;
void dfs1(int u)
{
    dep[u] = dep[fa[u]] + 1;
    siz[u] = 1;
    for(int i = head[u];i;i = edge[i].nxt)
    {
        int v = edge[i].to;
        dfs1(v);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]])
        {
            son[u] = v;
        }
    }
}
void dfs2(int u,int t)
{
    dfn[u] = ++timer;
    rev[timer] = u;
    top[u] = t;
    if(son[u])
    {
        dfs2(son[u],t);
    }
    for(int i = head[u];i;i = edge[i].nxt)
    {
        int v = edge[i].to;
        if(v == son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
}
int ans[max_n];
struct Query
{
    int u,v,lim,id,ans,cnt;
}ques[max_n];
struct Change
{
    int id,tim;
}changes[max_n];
int tree[max_n];
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x)
{
    for(;x <= n;x += lowbit(x))
    {
        tree[x]++;
    }
}
int query(int x)
{
    int res = 0;
    for(;x;x -= lowbit(x))
    {
        res += tree[x];
    }
    return res;
}
int query(int l,int r)
{
    return query(r) - query(l - 1);
}
signed main()
{
    read(n);
    for(int i = 1;i <= n;i++)
    {
        read(fa[i]);
        if(fa[i])
        {
            add(fa[i],i);
        }
        else
        {
            root = i;
        }
    }
    dfs1(root);
    dfs2(root,root);
    read(q);
    int cnt = 0;
    for(int i = 1,u,v,lim,op;i <= q;i++)
    {
        read(op);
        if(op == 2)
        {
            read(u);
            changes[i - cnt].id = u;
            changes[i - cnt].tim = i;
        }
        else
        {
            ++cnt;
            read(u),read(v),read(lim);
            ques[cnt].u = u;
            ques[cnt].v = v;
            ques[cnt].lim = lim;
            ques[cnt].id = i;
        }

    }
    sort(ques + 1,ques + cnt + 1,[](Query q1,Query q2){return (q1.id - q1.lim) < (q2.id - q2.lim);});;
    int now = 1;
    for(int i = 1;i <= cnt;++i)
    {
        while(now <= q - cnt && changes[now].tim < (ques[i].id - ques[i].lim))
        {
            update(dfn[changes[now].id]);
            ++now;
        }
        int u = ques[i].u,v = ques[i].v;
        ques[i].cnt = dep[u] + dep[v];
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]])
            {
                swap(u,v);
            }
            ques[i].ans += query(dfn[top[u]],dfn[u]);
            u = fa[top[u]];
        }
        if(dep[u] < dep[v])
        {
            swap(u,v);
        }
        ques[i].ans += query(dfn[v],dfn[u]);
        ques[i].cnt -= 2 * dep[v] - 1;
    }
    sort(ques + 1,ques + cnt + 1,[](Query q1,Query q2){return q1.id < q2.id;});
    for(int i = 1;i <= cnt;++i)
    {
        writesp(ques[i].cnt),writeln(ques[i].ans);
    }
    return 0;
}