難易度がC>>E>Fだと感じたし、正答数もそんなもんだけどなぜこの3問が150,140,130点なんだろうな。
http://tenka1-2015-final-open.contest.atcoder.jp/tasks/tenka1_2015_final_f
問題
N頂点の根付き木がある。
この木に対し、以下のクエリがQ個与えられるのでそれぞれ答えよ。
- 木中M個の頂点に実がなっている。subtreeにK個以上の実があるような頂点のうち、最も深い(根から遠い)頂点の深さを求めよ。
解法
Euler-Tour+LCAで解ける。
Euler-Tourの要領で、各頂点にDFS到達順で連番を付けておく。
またLCAを計算できるよう親のダブリングを済ませておく。
各クエリに対し、実のなる頂点をDFS到達順でソートした配列をVとする。
そしてLCA(V[i],V[i+K-1])が最も深い頂点を求め、その深さを返せばよい。
int N,Q,M,K; vector<int> E[101010]; int P[21][101010],D[100005]; int L[101010],R[101010],idt[101010]; int id=1; void dfs(int cur,int pre) { int i,p=-1; if(pre!=-1) D[cur]=D[pre]+1; P[0][cur]=pre; idt[id]=cur; L[cur]=id++; FOR(i,E[cur].size()) { int tar=E[cur][i]; if(tar==pre) p=i; else dfs(tar,cur); } R[cur]=id; if(p>=0) E[cur].erase(E[cur].begin()+p); } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } 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); E[y-1].push_back(x-1); } dfs(0,-1); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; cin>>Q; while(Q--) { cin>>M>>K; vector<int> v; while(M--) { cin>>x; v.push_back(L[x-1]); } sort(v.begin(),v.end()); int mad=0; for(i=0;i+K-1<v.size();i++) { x=idt[v[i]]; y=idt[v[i+K-1]]; mad=max(mad,D[lca(x,y)]); } cout<<mad<<endl; } }
まとめ
これはほとんど方針迷わなかったし、実際本番10分足らずで解いてる。
もう少し配点低くても良さそうだけど…CやEにもっと簡潔な解法があったりした?