【DS】P5311 [Ynoi2011] 成都七中

考虑点分树，找到最浅的满足条件的点，那么所有连通块符合条件的一定能以它为根来统计到。

考虑一个点 \(y\) 满足能作为颜色集合中（但不一定对答案贡献），显然是 \(x\to y\) 的路径所经过的点都满足那个偏序关系。

转化为二位偏序即可，数颜色 HH 的项链，大致按 r 排序，维护最大的 l 来贡献。

哈哈，我不会二位偏序（）

节省空间的话可以在建立点分树时就搞当前重心答案。

#include 
#define pb push_back
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
#define inf (int)(2e9)
#define N (int)(1e5+5)
struct node {
	int l,r,id;
	node(int lx,int rx,int idd) {
		l=lx; r=rx; id=idd;
	}
};
vectorg[N];
vectorQ[N],q,vec;
bool vis[N],used[N];
int n,m,ans[N],pre[N],sum[N],col[N],mi,rt,nwsum,sz[N];

int lowbit(int x) {
	return x&(-x);
}
void add(int x,int v) {
	if(x<=0) return ;
	while(x<=n) sum[x]+=v,x+=lowbit(x); 
}
int qry(int x) {
	if(x<=0) return 0;
	int res=0;
	while(x) res+=sum[x],x-=lowbit(x);
	return res;
}

void fd_rt(int x,int ff) {
	sz[x]=1; int qwq=0;
	for(int y:g[x]) {
		if(vis[y]||y==ff) continue;
		fd_rt(y,x); sz[x]+=sz[y];
		qwq=max(qwq,sz[y]);
	}
	qwq=max(qwq,nwsum-sz[x]);
	if(qwq=r) {
			used[qwq.id]=1; q.pb(node(qwq.l,qwq.r,qwq.id)); 
		}
	}
	for(int y:g[x]) {
		if(vis[y]||y==ff) continue;
		dfs(y,x,min(l,y),max(r,y));
	}
}

bool cmp(const node &x,const node &y) {
	return x.rpre[vec[j].id]) {
				add(pre[vec[j].id],-1);
				add(vec[j].l,1);
				pre[vec[j].id]=vec[j].l;
			}
			++j;
		}
	//	printf("%d %d %d\n",q[i].id,q[i].l,q[i].r);
		ans[q[i].id]=qry(q[i].r)-qry(q[i].l-1);
	}
	for(int i=0;i