P5311 [Ynoi2011] 成都七中题解

Gmt丶FFF · 2023-10-09 19:40:14 · 题解

树德蒟蒻瑟瑟发抖。

~~文化课差考不起七中~~

首先因为这题求的东西与连通块有关，又有多组询问，可以想到与点分树有关，因为点分树上的一棵子树在原树上是一个连通块。

~~然后建出点分树后，就不知道怎么做了~~。

实际上呢，对于每一个询问，存在点分树上的一个点 y\in[l,r] 包含整个 x 所在满足 \left[l,r\right] 限制的连通块。

证明是显然的，因为点分树最浅的在满足条件的联通块里的点子树为原树的连通块，此时若 x 在子树且 y 与 x 处于连通块中，其他的点也会包含在此连通块中，不然就会跑到点分树上 y 的祖先去了。

那么我们可以对于点分树上开始搜子树的节点，但是由于判 x 与 y 是否联通不能在点分树上判断，所以对于点分树上每一个点，在原树上进行搜索，记录路径上的最大编号与最小编号，搜到每个 x 时，就可以判断是否联通了。

那么我们可以对于树上每个点我们可以建一个 vector，这样把每个询问的 x push 进去即可。

现在我们就找到 y 了，那么连通块上的点就是 \text{路径上最大编号} \le r 且 \text{路径上最小编号}\ge l 的点。（~~这个就应该不用证了吧~~）

那么假设我们要求的是求联通块的大小，那么我们因为有很多个询问对应一个 y，所以我们相当于就是有许多询问 \left[l,r\right]，很多个点 \left[x,y\right]，求有多少个点满足 l\le x 且 y \le r，这很明显是个二维偏序问题，以 r,y 为第一关键字排序，扫描 r，在满足 y \le r 的情况下，用树状数组维护 x，根据 l 来求出树状数组中数字之和即可。

现在有颜色的限制，实际上也很简单，在维护树状数组的过程中，判断这个颜色之前是否也有相同颜色的点加入过树状数组，如果有，我们留下 x 更大的那个，这样造成的贡献更多，最后统一清空即可。

那么这样看下来，根本不需要建点分树了，点分治的途中维护即可。

但还是一打就打到头吧，最后还是建了点分树，~~主要是懒得改~~。

时间复杂度：O(n\log_2^2n)

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+5;
vector<int>a[N],b[N];
int n,m,rt,siz[N],mp[N],tot,vis[N],res[N],f[N],las[N],c[N],st[N],cnt;
struct node
{
    int id,l,r;
};
vector<node>q[N],p,w;
inline int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int k)
{
    while(x<=n)
    {
        f[x]+=k;
        x+=lowbit(x);
    }
}
int search(int x)
{
    int sum=0;
    while(x)
    {
        sum+=f[x];
        x-=lowbit(x);
    }
    return sum;
}
bool cmp(node x,node y)
{
    return x.r<y.r;
}
void findzx(int x,int fa)
{
    siz[x]=1;
    mp[x]=1;
    int len=a[x].size();
    for(int i=0;i<len;i++)
    {
        if(vis[a[x][i]]||a[x][i]==fa)continue;
        findzx(a[x][i],x);
        siz[x]+=siz[a[x][i]];
        mp[x]=max(mp[x],siz[a[x][i]]);
    }
    mp[x]=max(mp[x],tot-siz[x]);
    if(mp[rt]>mp[x])rt=x;
}
void divide(int x,int num)
{
    vis[x]=1;
    int len=a[x].size();
    for(int i=0;i<len;i++)
    {
        if(vis[a[x][i]])continue;
        if(siz[x]>siz[a[x][i]])tot=siz[a[x][i]];
        else tot=num-siz[x];
        rt=0;
        findzx(a[x][i],0);
        b[x].push_back(rt);
        divide(rt,tot);
    }
}
void dfs2(int x,int fa,int l,int r)
{
//  cout<<x<<" "<<fa<<" "<<l<<" "<<r<<endl;
    p.push_back({c[x],l,r});
    int len=q[x].size();
    for(int i=0;i<len;i++)if(!res[q[x][i].id]&&l>=q[x][i].l&&r<=q[x][i].r)w.push_back(q[x][i]);
    len=a[x].size();
    for(int i=0;i<len;i++)
    {
        if(a[x][i]==fa||vis[a[x][i]])continue;
        dfs2(a[x][i],x,min(l,a[x][i]),max(r,a[x][i]));
    }
}
void calc(int x)
{
    p.clear();
    w.clear();
//  cout<<x<<" :\n";
    dfs2(x,0,x,x);
    sort(p.begin(),p.end(),cmp);
    sort(w.begin(),w.end(),cmp);
    int head=0;
    int len=p.size(),len2=w.size();
    for(int i=0;i<len2;i++)
    {
//      cout<<x<<" "<<w[i].id<<"\n";
        while(head<len&&p[head].r<=w[i].r)
        {
//          cout<<head<<endl;
            if(!las[p[head].id])update(p[head].l,1),las[p[head].id]=p[head].l,st[++cnt]=p[head].id;
            else if(p[head].l>las[p[head].id])update(las[p[head].id],-1),update(p[head].l,1),las[p[head].id]=p[head].l;
//          cout<<head<<endl;
            head++;
        }
        res[w[i].id]=search(n)-search(w[i].l-1);
//      cout<<"!!\n";
    }
//  cout<<"///";
    while(cnt)update(las[st[cnt]],-1),las[st[cnt]]=0,cnt--;
}
void dfs(int x)
{
    calc(x);
    vis[x]=1;
    int len=b[x].size();
    for(int i=0;i<len;i++)dfs(b[x][i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    mp[0]=2e9;
    tot=n;
    findzx(1,0);
    int root=rt;
    divide(rt,n);
    for(int i=1;i<=m;i++)
    {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        q[x].push_back({i,l,r});
    }
    for(int i=1;i<=n;i++)vis[i]=0;
    dfs(root);
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}

P5311 [Ynoi2011] 成都七中 题解

P5311 [Ynoi2011] 成都七中题解