問題
http://community.topcoder.com/stat?c=problem_statement&pm=13746&rd=16434
解き方
木のルートからDFSでたどっていってパスの数を足していけば良い。
ルート０に直接つながっているノードについて、
さらにその下にノードがつながっていればそのパスの和、
つながっていなければ１を返す。
コード
vector<int> p;
int n;
class UnrelatedPaths {
public:
int dfs(int x){
int ret=0;
FORE(i,0,n)if(p[i]==x){
ret+=dfs(i+1);
}
return ret==0 ? 1 : ret;
}
int maxUnrelatedPaths(vector<int> parent) {
p=parent;
n=p.size();
return dfs(0);
}
};
int n;
class UnrelatedPaths {
public:
int dfs(int x){
int ret=0;
FORE(i,0,n)if(p[i]==x){
ret+=dfs(i+1);
}
return ret==0 ? 1 : ret;
}
int maxUnrelatedPaths(vector<int> parent) {
p=parent;
n=p.size();
return dfs(0);
}
};