P9340 [JOISC 2023] Tourism (Day3) 题解

· · 题解

题目传送门

前置知识

珂朵莉树/颜色段均摊 | 树状数组 | 扫描线

解法

考虑对 a_{i} 扫描线后柯朵莉树在链上进行区间覆盖，然后转化为查询颜色 \in [l,r] 内的点的个数，可以使用树状数组维护。

当然，也可以无脑直接覆盖到根节点，然后对区间 \operatorname{LCA} 的根链进行容斥，求一遍区间内 DFS 序最小和最大的两个点的 \operatorname{LCA} 即可。

代码中写的是对 (a_{i-1},a_{i}) 这条链进行覆盖的写法。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
    int nxt,to;
}e[200010];
int head[200010],fa[200010],siz[200010],dep[200010],son[200010],top[200010],dfn[200010],ans[200010],a[200010],tot=0,cnt=0;
vector<pair<int,int> >q[200010];
void add(int u,int v)
{
    cnt++;  e[cnt]=(node){head[u],v};  head[u]=cnt;
}
void dfs1(int x,int father)
{
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i!=0;i=e[i].nxt)  if(e[i].to!=father)
    {
        dfs1(e[i].to,x);
        siz[x]+=siz[e[i].to];
        son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
    }
}
void dfs2(int x,int id)
{
    top[x]=id;
    tot++;  dfn[x]=tot;
    if(son[x]!=0)
    {
        dfs2(son[x],id);
        for(int i=head[x];i!=0;i=e[i].nxt)  
        {
            if(e[i].to!=fa[x]&&e[i].to!=son[x])  dfs2(e[i].to,e[i].to);
        }   
    }
}
struct BIT
{
    int c[200010];
    int lowbit(int x)
    {
        return (x&(-x));
    }
    void add(int n,int x,int val)
    {
        if(x==0)  return;
        for(int i=x;i<=n;i+=lowbit(i))  c[i]+=val;
    }
    int getsum(int x)
    {
        int ans=0;
        for(int i=x;i>=1;i-=lowbit(i))  ans+=c[i];
        return ans;
    }
}T;
struct ODT
{
    struct node
    {
        int l,r;
        mutable int col;
        bool operator < (const node &another) const
        {
            return l<another.l;
        }
    };
    set<node>s;
    void init(int n)
    {
        s.insert((node){1,n,0});
    }
    set<node>::iterator split(int pos)
    {
        set<node>::iterator it=s.lower_bound((node){pos,0,0});
        if(it!=s.end()&&it->l==pos)  return it;
        it--;
        if(it->r<pos)  return s.end();
        int l=it->l,r=it->r,col=it->col;
        s.erase(it);
        s.insert((node){l,pos-1,col});
        return s.insert((node){pos,r,col}).first;
    }
    void assign(int l,int r,int col,int n)
    {
        set<node>::iterator itr=split(r+1),itl=split(l);
        for(set<node>::iterator it=itl;it!=itr;it++)  T.add(n,it->col,-(it->r-it->l+1));
        T.add(n,col,r-l+1);
        s.erase(itl,itr);
        s.insert((node){l,r,col});
    }
}O;
void update(int u,int v,int col,int n)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
        {
            O.assign(dfn[top[u]],dfn[u],col,n);
            u=fa[top[u]];
        }
        else
        {
            O.assign(dfn[top[v]],dfn[v],col,n);
            v=fa[top[v]];
        }
    }
    if(dep[u]<dep[v])  O.assign(dfn[u],dfn[v],col,n);
    else  O.assign(dfn[v],dfn[u],col,n);
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m,k,u,v,i,j;
    cin>>n>>m>>k;
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        add(u,v);  add(v,u);
    }
    for(i=1;i<=m;i++)  cin>>a[i];
    for(i=1;i<=k;i++)
    {
        cin>>u>>v;
        if(u==v)  ans[i]=1;
        else  q[v].push_back(make_pair(u,i));
    }
    dfs1(1,0);  dfs2(1,1);  O.init(n);
    for(i=2;i<=m;i++)
    {
        update(a[i-1],a[i],i,m);
        for(j=0;j<q[i].size();j++)  ans[q[i][j].second]=T.getsum(i)-T.getsum(q[i][j].first);
    }
    for(i=1;i<=k;i++)   cout<<ans[i]<<endl;
    return 0;
}