Codeforces Global Round 6 : F. Almost Same Distance

これはけっこうしんどい…。
https://codeforces.com/contest/1266/problem/F

問題

木を成すN頂点の無向グラフが与えられる。
頂点集合の部分集合がおおよそkに統一されているとは、集合内の頂点間の距離がkかk+1であることとする。
k=1～Nに対し、おおよそkに統一されている点の集合の最大要素数を求めよ。

解法

• k=1の時は、ある点とその隣接点群で自明。
• k=2l+1の時、ある中心点vから、距離lまたはl+1の点のうち辺を共有しないものを列挙したものとなる。ただし距離lの点は1個までしか許可されない。
• k=2lの時、一つは中心点vから、距離lまたはl+1の点のうち辺を共有しないものを列挙したものとなる。ただし距離l+1の点は1個までしか許可されない。
  • もう一つの例として、中心点を2つu-vととり、u側及びv側に距離lの点を取ったもの

全方位DPの要領で、各点vに対し、各隣接点の奥にある最遠点の配列を持てば、上記lと対応する点数を列挙できる。
同じく辺に対しても最遠点配列をもって処理していく。

int N;
vector<pair<int,int>> E[505050];
map<int,int> M[505050];
int MD[505050];

int ret[505050];

int dfs(int cur,int pre) {
	int i;
	int ma=0;
	FOR(i,E[cur].size()) if(E[cur][i].first!=pre) {
		E[cur][i].second=dfs(E[cur][i].first,cur)+1;
		ma=max(ma,E[cur][i].second);
	}
	return ma;
}
void dfs2(int cur,int pre,int pard) {
	vector<int> V;
	V.push_back(0);
	V.push_back(0);
	int i;
	FOR(i,E[cur].size()) {
		if(E[cur][i].first==pre) E[cur][i].second=pard;
		V.push_back(E[cur][i].second);
	}
	sort(ALL(V));
	reverse(ALL(V));
	FOR(i,E[cur].size()) if(E[cur][i].first!=pre) {
		if(V[0]==E[cur][i].second) dfs2(E[cur][i].first,cur,V[1]+1);
		else dfs2(E[cur][i].first,cur,V[0]+1);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back({y-1,0});
		E[y-1].push_back({x-1,0});
	}
	dfs(0,0);
	dfs2(0,0,0);
	
	FOR(i,N) {
		ret[1]=max(ret[1],1+(int)E[i].size());
		vector<int> V;
		FORR(e,E[i]) V.push_back(e.second);
		sort(ALL(V));
		FORR(v,V) M[i][-v]++;
		FOR(x,V.size()) {
			ret[V[x]*2]=max((int)ret[V[x]*2],(int)V.size()-x);
			if(x<V.size()-1&&V[x+1]>V[x]) {
				ret[V[x]*2+1]=max((int)ret[V[x]*2+1],(int)V.size()-x);
			}
			else {
				ret[V[x]*2-1]=max((int)ret[V[x]*2-1],(int)V.size()-x);
			}
		}
	}
	
	FOR(i,N) FORR(e,E[i]) if(e.first<i) {
		x=i;
		y=e.first;
		if(M[x].size()<M[y].size()) swap(x,y);
		FORR(m,M[y]) M[x][m.first]+=m.second;
		int sum=0;
		FORR(m,M[x]) {
			sum+=m.second;
			ret[-m.first*2]=max(ret[-m.first*2],sum-2);
		}
		FORR(m,M[y]) M[x][m.first]-=m.second;
	}
	
	
	for(i=N;i>=1;i--) ret[i]=max({ret[i],ret[i+2],1});
	for(i=1;i<=N;i++) cout<<ret[i]<<" ";
	cout<<endl;
	
}

まとめ

E→Fで難易度変わりすぎ？