Codeforces #1001 : E2. The Game (Hard Version)

うーむ。
https://codeforces.com/contest/2062/problem/E2

問題

問題設定はEasyと同じ。代わりに、初手必勝となる点をすべて列挙せよ。
Codeforces #1001 : E1. The Game (Easy Version) - kmjp's blog

解法

後手が点uを選んだ時、初手で点vを選んだ時に次に先手が駒を動かせない条件を考えると、以下のいずれかである。

• uよりも設定値が多い点xを列挙したとき、vがそれらをすべてSubTreeに含む、すなわちそれらのxのLCAまたはその祖先である。
• 後手がuを選べない、すなわちvがuの祖先である

初手点vで必勝となる条件は、vのSubTree外に設定値がvより大きな点uが1個以上あり、かつ各点uに対し、点vが上記条件を満たすことである。

設定値が多い順に処理していく。uに対し、vがuまたはxのLCAの祖先があればよい。
頂点をあらかじめDFS順に並べ替えておき、BITを使いuの位置をインクリメント、xのLCAの位置をインクリメント、uと(xのLCA)のLCAの位置をデクリメントしておこう。
こうすると、「vがuまたはxのLCAの祖先である」場合にのみBITを参照した結果が1になるようにできる。
全uに対するBITの加算結果が、uの個数と一致するなら点vは初手必勝の点となる。

int T;
int N;
int W[404040];
vector<int> E[404040];

const int ME=400001;
int L[ME],R[ME],D[ME],P[ME],rev[ME];
vector<int> Vs[404040];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;


void EulerTour(int cur,int pre=-1,int d=0) {
	static int eid;
	if(pre==-1) eid=0, pre=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>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) Vs[i].clear();
		FOR(i,N) {
			cin>>W[i];
			E[i].clear();
			W[i]--;
			Vs[W[i]].push_back(i);
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		EulerTour(0);
		FOR(i,N) st.update(L[i],W[i]);
		
		int ret=0;
		FOR(i,N) {
			x=max(st.getval(0,L[i]),st.getval(R[i],N));
			if(x>W[i]&&(ret==0||W[i]>W[ret-1])) ret=i+1;
		}
		cout<<ret<<endl;
	}
}

まとめ

これ結構難しいと思うけど、AC数そこそこいるんだよな…。