Hackerrank 101 Hack Jan 2016 Longest Path
Longest Path
問題
木が与えられる。頂点は白黒に塗り分けられている。 黒い頂点のみからなる道で最長のものの長さを答えよ。
解法
黒い頂点による各連結成分について直径を取る。
実装
#include <iostream>
#include <vector>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
pair<int,int> dfs(int i, int p, vector<bool> const & c, vector<vector<int> > const & g) {
int depth = 0;
int z = i;
for (int j : g[i]) if (j != p and c[j]) {
int ndepth, nz; tie(ndepth, nz) = dfs(j, i, c, g);
if (depth < ndepth) {
depth = ndepth;
z = nz;
}
}
return { depth + 1, z };
}
void use(int i, vector<bool> & usable, vector<vector<int> > const & g) {
usable[i] = false;
for (int j : g[i]) if (usable[j]) use(j, usable, g);
}
int main() {
int n; cin >> n;
vector<bool> c(n); repeat (i,n) { int it; cin >> it; c[i] = it; }
vector<vector<int> > g(n);
repeat (i,n-1) {
int j; cin >> j; -- j;
g[i+1].push_back(j);
g[j].push_back(i+1);
}
int ans = 0;
repeat (i,n) if (c[i]) {
int depth, j;
tie(depth, j) = dfs(i, -1, c, g);
tie(depth, j) = dfs(j, -1, c, g);
ans = max(ans, depth);
use(j, c, g);
}
cout << ans << endl;
return 0;
}