Codeforces ECR #116 : F. Tree Queries

ECRボス問はこういうのしばしば見る気がする。
https://codeforces.com/contest/1606/problem/F

問題

根付き木が与えられる。
その後、以下のクエリが与えられるので順次答えよ。
各クエリは頂点vとパラメータkで与えられる。

以下、コストをk払うと、1つ任意の頂点を削除できる。
その際、削除した頂点の子頂点は、削除した親頂点の子となる。

最適な削除を行ったとき、(頂点vの子頂点数)-(コスト)の最大値を求めよ。

解法

kが小さいほどたくさん頂点を消してよくなる。
そこで、kを200000～0までだんだん減少させながら、各頂点(頂点vの子頂点数)-(コスト)が最大となるよう更新させていこう。
各頂点、子頂点の数がk以下になったら削除した方が親は得をする。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> vnum,vdel;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;

int N;

int Q,V[202020],K[202020],ret[202020];

const int ME=300001;
vector<int> E[ME];
int L[ME],R[ME],D[ME],P[ME],rev[ME],eid;
int vis[202020];
int top[202020];
set<int> del[202020];
vector<int> query[202020];


void EulerTour(int cur,int pre=0,int d=0) {
	if(pre==-1) ZERO(L),ZERO(R),eid=0;
	rev[eid]=cur;
	P[cur]=pre;
	L[cur]=eid++;
	D[cur]=d;
	FORR(e,E[cur]) if(e!=pre) EulerTour(e,cur,d+1);
	R[cur]=eid;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	E[0].push_back(1);
	E[1].push_back(0);
	N++;
	
	EulerTour(0);
	FOR(i,N) {
		top[i]=L[i];
		vnum.add(L[i],E[i].size()-1);
		if(i) vnum.add(L[P[i]],-((int)E[i].size()-1));
		if(i>1&&E[i].size()>=2) del[E[i].size()-2].insert(-L[i]);
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>V[i]>>K[i];
		query[K[i]].push_back(i);
	}
	
	for(k=200000;k>=0;k--) {
		while(del[k].size()) {
			int v=rev[-*del[k].begin()];
			del[k].erase(del[k].begin());
			if(vis[v]) continue;
			vis[v]=1;
			top[uf[v]]=top[uf[P[v]]]=min(top[uf[v]],top[uf[P[v]]]);
			uf(v,P[v]);
			x=vnum(R[v]-1)-vnum(L[v]-1);
			i=vdel(R[v]-1)-vdel(L[v]-1);
			y=rev[top[uf[v]]];
			vnum.add(L[P[v]],x-1);
			vnum.add(L[P[y]],-x+1);
			vdel.add(L[P[v]],i+1);
			vdel.add(L[P[y]],-(i+1));
			if(y>1&&vis[y]==0) {
				x=vnum(R[y]-1)-vnum(L[y]-1);
				i=vdel(R[y]-1)-vdel(L[y]-1);
				x=max(0,min(k,(x+i)/(i+1)-1));
				del[x].insert(-L[y]);
			}
		}
		FORR(q,query[k]) {
			int v=V[q];
			ret[q]=(vnum(R[v]-1)-vnum(L[v]-1))-1LL*k*(vdel(R[v]-1)-vdel(L[v]-1));
		}
	}
	
	
	
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

クエリをうまく並べ替えると良い感じで解ける問題、さっと対応できないんだよな。