P8575 「DTOI-2」星之河 题解

· · 题解

首先拿到题，不难发现如果给定的不是一棵树而是序列，那就是完全的板子题。

考虑如何向原问题转化：当然是要按照某个“序”将树变成序列，那怎么知道应该按照什么“序”呢？

让我们回归问题本身，题目要求的是求每个节点为根的子树内的二维偏序，那这个“序”当然需要满足同一子树内的节点在“序”中编号都大于/小于根节点，容易想到 dfs 序就满足条件。

  1. red_v \leq red_u
  2. blue_v \leq blue_u
  3. dfn_u < dfn_v < dfn_u + sz_u

那么直接做三维偏序就行了，下附代码：


#include<bits/stdc++.h>
using namespace std;
#define lowbit(x)   x&-x
#define mid ((L+R)>>1)
const int N=2e5+10;
int n,now,ans[N],C[N];
int h[N],e[N<<1],ne[N<<1],idx;
struct node
{
    int red,blue,dfn,sz,id;
    bool operator<(const node other)const
    {
        if(red!=other.red)  return red<other.red;
        if(blue!=other.blue)    return blue<other.blue;
        return dfn>other.dfn;
    }
}p[N],tmp[N];
inline void link(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline void dfs(int u,int fa)
{
    p[u].dfn=++now;
    p[u].sz=1;
    for(int i=h[u];~i;i=ne[i])
    {
        if(e[i]==fa)    continue;
        dfs(e[i],u);
        p[u].sz+=p[e[i]].sz;
    }
}
inline void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x)) C[x]+=y;
}
inline int query(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))    ans+=C[x];
    return ans;
}
inline void mergesort(int L,int R)
{
    if(L==R)    return void();
    mergesort(L,mid);
    mergesort(mid+1,R);
    int i=L,j=mid+1,t=0;
    while(i<=mid&&j<=R)
        if(p[i].blue<=p[j].blue)    add(p[i].dfn,1),tmp[++t]=p[i],i++;
        else ans[p[j].id]+=query(min(p[j].dfn+p[j].sz-1,n))-query(p[j].dfn),tmp[++t]=p[j],j++;
    while(i<=mid)   add(p[i].dfn,1),tmp[++t]=p[i],i++;
    while(j<=R) ans[p[j].id]+=query(min(p[j].dfn+p[j].sz-1,n))-query(p[j].dfn),tmp[++t]=p[j],j++;
    for(int i=L;i<=mid;i++) add(p[i].dfn,-1);
    for(int i=L,j=1;i<=R;i++,j++)   p[i]=tmp[j];
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   p[i].id=i;
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        link(u,v),link(v,u);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)   scanf("%d%d",&p[i].red,&p[i].blue);
    sort(p+1,p+n+1);
    mergesort(1,n);
    for(int i=1;i<=n;i++)   if(ans[i])  printf("%d\n",ans[i]);
    return 0;
}