AtCoder ABC #165 : F - LIS on Tree

そういやこの後LeetCode Biweeklyもあるのか。
https://atcoder.jp/contests/abc165/tasks/abc165_f

問題

頂点1番を根とする付き木を成す無向グラフが与えられる。
各頂点には正整数が設定されている。

各頂点kに対し、頂点1→kのパス上の頂点の設定値を並べた整数列に対するLISの長さを求めよ。

解法

LISの手順では、数列に要素が1個加わるたびに配列を1か所更新する。
ここで、更新した内容を戻すことができれば、DFS順で木を探索しつつ、そのつどLISの状態を保持できる。

そこで、DFSで頂点の処理を始めるときに、LISを求めるための配列を更新しよう。
その際、更新前の値と更新位置を覚えておこう。
DFS後関数を抜ける際に、更新分を戻せばよい。

int N;
int A[201010];
vector<int> V;
int ret[201010];
vector<int> E[201010];

void dfs(int cur,int pre) {
	int pos=lower_bound(ALL(V),A[cur])-V.begin();
	int rev;
	if(pos==V.size()) {
		rev=-1;
		V.push_back(A[cur]);
	}
	else {
		rev=V[pos];
		V[pos]=A[cur];
	}
	ret[cur]=V.size();
	
	
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
	
	if(rev==-1) {
		V.pop_back();
	}
	else {
		V[pos]=rev;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	
	FOR(i,N) cout<<ret[i]<<endl;
}

まとめ

問題が多い…。