Codeforces #1001 : E1. The Game (Easy Version)

Easyでもちょっと悩む。
https://codeforces.com/contest/2062/problem/E1

問題

与えられた根付き木を使った、2人対戦ゲームを考える。
各点には値が設定されている。

初手は任意の点を指定し駒を置ける。以降は、前の人の駒を置いた点の設定値より、大きな値の点に駒を置ける。
ただし、一旦駒を置くとそのSubTreeの点は消滅する。

自身の手番で駒を移動できない場合、価値となる。
初手で勝ちとなる駒の位置を1つ答えよ。

解法

初手で各点vに置いた場合、少なくとも後手が置ける点が1個以上あるかを判定しよう。
これは区間最大値を取るSegTreeを用い、vのSubtree外に設定値がvより大きい点があるかを見ればよい。

候補が複数ある場合、そのうち設定値が最大のvを選べば、後手の選べる点は1つになり、その後先手は駒を移動できなくなる。

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;
	}
}

まとめ

こっちはまだいいんだけどね。