P3252 [JLOI2012] 树

flyinglandlord · 2017-12-09 00:50:47 · 题解

简单题，两层DFS，一定用链式前向星存树（别问我怎么知道的）！！

主要代码如下：

``cpp

class Tree_Route {
    #define maxn 100000
    struct node {
        int v;
        int next;
    }e[maxn];
    int tot = 0, front[maxn];

public :

        int N,S;
        int list[maxn];
        int cnt;
    private : int Addedge(int u, int v) {
        tot++;
        e[tot].v = v;
        e[tot].next = front[u];
        front[u] = tot;
    }
    public : int Readin() {
        ios::sync_with_stdio(false);
        cin >> N >> S;
        for(int i=1;i<=N;i++) cin >> list[i];
        for(int i=1;i<=N-1;i++) {
            int fa, son;
            cin >> fa >> son;
            Addedge(fa, son);
        }
        cnt = 0;
    }
    public : int dfs(int now, int cur) {
        int sum=0;
        //cout << now << endl;
        if(cur == S) return 1;
        else if(cur > S) return 0;
        for(int i=front[now];i!=0;i=e[i].next) {
            sum += dfs(e[i].v, cur + list[e[i].v]);
        }
        return sum;
    }
    public : int Main_Process(int root) {
        cnt += dfs(root, list[root]);
        //cout << root << endl;
        for(int i=front[root];i!=0;i=e[i].next) {
            Main_Process(e[i].v);
        }
    }
}solver;