团体程序设计天梯赛(L2-020 功夫传人 (25 分))

题目:团体程序设计天梯赛(L2-020 功夫传人 (25 分))

思路分析:

就是一个简单的暴力dfs遍历树的问题  建树可以用邻接表来实现!

代码实现:

const int MAX=100100;
vector<int>v[MAX];
int t[MAX];
int n;
double k,z;
double ans;
double val[MAX];
void dfs(int u){
    if(t[u]) ans+=val[u];
    for(int i=0;i<v[u].size();i++){
        int ne=v[u][i];
        val[ne]=val[u]*z;
        
        if(t[ne]) val[ne]*=t[ne];
//        cout<<ne<<" = "<<val[ne]<<endl;
        dfs(ne);
    }
}
int main(){
    cin>>n>>k>>z;
    z=(100-z)/100.0;
//    cout<<z<<endl;
    for(int i=0;i<n;i++){
        int m;
        cin>>m;
        if(m==0){
            int x;
            cin>>x;
            t[i]=x;
        }
        else {
            while (m--) {
                int x;
                cin>>x;
                v[i].push_back(x);
            }
        }
    }
    val[0]=k;
    dfs(0);
    
    printf("%d",int(ans));
}

上一篇:2-两数相加


下一篇:2.两数相加