ABC202 E 解答

E - Count Descendants（1638）

問題

E - Count Descendants

問題文

N 頂点の根付き木があり、頂点は 1, 2, … , Nと番号付けられています。
頂点 1 が根であり、頂点 i ( 2 ≤ i ≤ N ) の親は Pi です。
Q 個のクエリが与えられます。i ( 1 ≤ i ≤ Q ) 番目のクエリでは、整数 Ui, Diが与えられるので、次の条件を全て満たす頂点 u の個数を求めてください。
・u から根への最短パス上（端点も含む）に頂点 Ui が存在する。
・uから根への最短パスに含まれる辺の数がちょうど Di である。

制約

2 ≤ N ≤ 2×10^5
1 ≤ Pi < i
1 ≤ Q ≤ 2×10^5
1 ≤ Ui ≤ N
0 ≤ Di ≤ N−1
入力は全て整数である。

考察

まずは、各クエリの条件を見ていきましょう。条件は２つありますね。

・u から根への最短パス上に頂点 Ui が存在する
・u から根への最短パスに含まれる辺の数がちょうど Diである

です。本問題におけるグラフは木ですのでちょっとだけ言い換えができそうです。図を用いて説明します。

Ui = 5
Di = 3

としましょうか。

2つのクエリを分けて考えます。

・Ui=5が最短パス上に含まれる

となりますと該当するのはこの４つですかね。もうちょっというのであれば、Uiおよびその子が該当します。

・Di = 3

こうですね。この条件は根（０）からの距離、深さが３のものが該当します。

以上の２つの条件を「両方」満たすものが今回求めたい頂点数となります。ということで、該当するのは「８，９，１０」の３つですね。このクエリの答えは３となります。

このように、各クエリでは

Uiの子
かつ
深さがDiのもの

を答えることになります。

次にこの要求に答える方法を考えます。これ、「Uiの子」という条件がなければ簡単に求めることができます。一回このグラフを探索していしまえば各頂点の深さが求まりますので、あとはちょちょいとやるだけです。

「Uiの子」が面倒くさいなら全部「Uiの子」にしてしまいましょう。次のグラフです。

このグラフだけなら答えが求められそうです。まず各頂点の深さを求めます。今回のクエリでは深さ3が求めらていますので、頂点5までの深さの２を引いて

頂点５からの深さが１の頂点の数

を求めるという課題に置き換えられます。

これを元のグラフで行いたいのですが、どうすればよいのでしょうか。よくわかりませんので、一旦、アルゴリズム、競プロ、プログラムなどは一切忘れて、ボードゲームをやる感覚でグラフを動いてみましょう。動く順番は左からどんどん下って行って、一番下まで行ったら分岐点まで戻ってきます。

とすると、次のような道で全部辿れます。

ここであなたは非常にマメ正確でして、各頂点に到着する前と各頂点を出る（来た道を戻る）際に今までに通った頂点の深さをメモしたくなりました。メモしたものが次になります。

ごちゃごちゃしましたがこれが探索結果になります。値を増やすのはその頂点から戻るときということに注意します。

ここで、頂点5の左右の差を取ってみましょう。

0 : 0
1 : 0
2 : 1
3 : 3

この値って先ほどの頂点5が根であるときの構造に似ていませんか？この値を用いることでクエリに答えることが可能となりそうです。実際の探索ではクエリ処理で求められている、深さ３の情報を保持しておけば良さそうです。

この手法なら1回探索するだけで色々なクエリに答えることが可能となります。与えられるクエリを先に読み込むことでこのクエリたちに答えていきましょう。

さて、最後に探索です。といってもDFSでこの順番通りに行うだけです。この辺はソースコードを見ながら確認してみてください。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int M = 2e5;

vector<vector<int>> g;
vector<vector<P>> query;
int used[M + 5];
int num[M + 5];
int ans[M + 5];

void dfs(int s, int depth)
{
   //頂点Ui=sのクエリを格納
   for (auto [qd, qi] : query[s])
   {
       //クエリqi番目の次数qdの頂点数（頂点に到達前）
       ans[qi] = -num[qd];
   }
   for (auto a : g[s])
   {
       if (used[a] == 1) continue;
       used[a] = 1;
       dfs(a, depth + 1);
   }
   //戻るときに頂点数を増やす
   ++num[depth];
   for (auto [qd, qi] : query[s])
   {
       //戻るときとの差分を計算
       ans[qi] += num[qd];
   }
}
int main()
{
   int n, q;
   cin >> n;
   g.resize(n);
   reps(i, 1, n)
   {
       int p; cin >> p;
       --p;
       g[p].emplace_back(i);
       g[i].emplace_back(p);
   }
   cin >> q;
   query.resize(n);
   //出力の関係上クエリ順は保持しておく必要がある
   rep(i, q)
   {
       int u, d; cin >> u >> d;
       --u;
       query[u].emplace_back(d, i);
   }
   used[0] = 1;
   dfs(0, 0);

   rep(i, q) cout << ans[i] << endl;
   return 0;
}

あとがき

グラフでクエリを処理する問題でした。クエリの先読みというやつですね。先読みというと特別な感じがしてしまいますが、何かを処理してからクエリに答える問題もいわば、先処理の問題といえるんじゃないのでしょうか。クエリを先に行うか、処理を先に行うかの違いだけですので、あまり恐れずに挑んでいただければと思います。

また、本問題のようにdfsで通った順番に何か処理をするものは「オイラーツアー」というみたいですね（正確じゃなかったらすみません）。とってもかっこいいです。この問題が解けたら「俺、オイラーツアーできるよ」と声に出したい日本語ランキング上位に食い込みそうなセリフを使うことができます。うん、言ってみたいです。

本問題のようにDFSをしながらグローバルで情報を管理する、という探索問題が最近多いような気がしています。これも典型なんですかね。しっかりと復習をして次はコンテスト中に通したいです！

類題といっていいかわかりませんが、紹介をしておきます。グローバルで管理するやつです。

E - Unique Color

この問題diffが緑なんですね。びっくりしました。もうちょっと難しいと思うんだけどな。こちらも解説がありますので、良ければどうぞ。