Expert.
Put your skills to the test.

Problem summary

A directed tree rooted at 1 has K proposed ancestor-to-descendant paths. Count subsets of proposals whose union covers every vertex, modulo 1000000007. Duplicate proposals are distinct choices.

Constraints

1 ≤ N ≤ 5000; 1 ≤ K ≤ 200000.

Worked example

Official statement example.

6
1 2
2 3
2 4
1 5
5 6
6
1 3
1 4
5 6
1 5
1 5
2 3

12

Solution analysis

1. Assign every proposed path to its endpoint. For a subtree rooted at u, count selections of all proposals assigned inside it that cover every vertex of that subtree. Their influence above u is summarized by the minimum depth of any selected start: because all paths are downward, a start at depth d≤depth(u) lies on u’s ancestor chain.
2. Store S[u][d], the number of valid selections whose minimum start depth is at least d, for 0≤d≤depth(u). Before requiring u itself covered, the analogous count F[d] is the product of S[child][d] over children, multiplied by 2 to the number of proposals ending at u whose starts have depth at least d. The factors are independent choices with disjoint endpoint sets.
3. Selections counted by F[depth(u)+1] leave u uncovered: every selected path starts strictly below u. Therefore S[u][d]=F[d]−F[depth(u)+1]. Evaluate thresholds downward, adding local start counts as their depths become available. The answer is S[root][0]. In the sample path ending at leaf 4 is forced, and combining leaf coverage and the duplicate 1→5 proposals yields 12 subsets.

Why it works

Inductively child tables count exactly selections covering their subtrees with the specified minimum-depth threshold. A minimum threshold on the union holds exactly when it holds in every independent child and for every chosen local proposal, proving the product formula. Once children are covered, the only unchecked vertex is u; it is uncovered exactly when all chosen starts are deeper than u. Subtracting these choices establishes the table invariant. At the root all vertices are checked and threshold zero imposes no restriction, giving precisely all covering subsets.

Watch out. A path is owned by its endpoint, not its start. Duplicate proposals contribute independent powers of two. Use an iterative tree order for long chains.

An independently written complete program with standard headers.

// Key idea: Inductively child tables count exactly selections covering their subtrees with the
// specified minimum-depth threshold. A minimum threshold on the union holds exactly when it holds in
// every independent child and for every chosen local proposal, proving the product formula.
#include<iostream>
#include<vector>
using namespace std;
const long long mod=1000000007;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>children(n);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        children[u-1].push_back(v-1);
    }
    vector<int>order{0},depth(n);
    for(size_t i=0;i<order.size();++i){
        int u=order[i];
        for(int v:children[u]){
            depth[v]=depth[u]+1;
            order.push_back(v);
        }
    }
    int k;
    cin>>k;
    vector<vector<int>>starts(n);
    for(int i=0;i<k;++i){
        int s,e;
        cin>>s>>e;
        starts[e-1].push_back(depth[s-1]);
    }
    vector<long long>powers(k+1,1);
    for(int i=1;i<=k;++i){
        powers[i]=powers[i-1]*2%mod;
    }
    vector<vector<int>>suffix(n);
    for(int index=n-1;index>=0;--index){
        int u=order[index];
        int h=depth[u];
        vector<int>count(h+1);
        for(int d:starts[u]){
            ++count[d];
        }
        long long uncovered=1;
        for(int v:children[u]){
            uncovered=uncovered*suffix[v][h+1]%mod;
        }
        suffix[u].resize(h+1);
        int available=0;
        for(int d=h;d>=0;--d){
            available+=count[d];
            long long value=powers[available];
            for(int v:children[u]){
                value=value*suffix[v][d]%mod;
            }
            suffix[u][d]=static_cast<int>((value-uncovered+mod)%mod);
        }
    }
    cout<<suffix[0][0]<<'\n';
}