国际大学生程序设计竞赛例题_4.7游戏

1,题意:求两个子集的深度之和.
2,解决:已知根节点为0,dfs一次,求得各节点深度即可.
3,实现代码:

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=10;

struct node
{
    int v;//孩子结点
};

//注意vector在树问题中的使用
vector<node> tree[maxn];

int depth[maxn]; //记录节点对应的深度
void dfs(int m,int f,int dep) //当前节点编号,父节点编号,深度
{
    depth[m]=dep;
    for(unsigned i=0;i<tree[m].size();i++)
    {
        if(tree[m][i].v==f)
            continue;
        dfs(tree[m][i].v,m,dep+1);
    }
}

int main()
{
    freopen("4.7.in","r",stdin);
    int n,m1,m2;//节点数
    int ans1,ans2;
    while(cin>>n>>m1>>m2)
    {
        ans1=0;
        ans2=0;
        for(int i=0;i<n;i++)
            tree[i].clear();
        int s,t;
        n--;
        while(n--)
        {
            node temp;
            cin>>s>>t;
            temp.v=t;
            tree[s].push_back(temp);
            temp.v=s;
            tree[t].push_back(temp);
        }
        dfs(0,-1,0);
        int u;
        while(m1--) cin>>u,ans1+=depth[u];
        while(m2--) cin>>u,ans2+=depth[u];
        cout<<(ans1<=ans2? "Bob":"Alice")<<endl;
    }
    return 0;
}