Proficient.
Put your skills to the test.

Problem summary

Count ordered seven-tuples (a,b,c,d,e,f,g) of distinct vertices in a tree such that ab, bc, bd, be, df and dg are edges. These roles describe a head, chest, two arms, waist and two feet. Exchanging left and right creates a different figure. Return the count modulo 1,000,000,007.

Constraints

1 ≤ n ≤ 10⁶; vertex labels are in [1,n]; the graph is a tree.

Worked example

An independently prepared example for this explanation.

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

12

Solution analysis

1. Fix the directed central edge b→d. Once this edge is fixed, the head a and arms c,e are three distinct ordered neighbors of b other than d. There are (deg(b)−1)(deg(b)−2)(deg(b)−3) choices.
2. The feet f,g are two distinct ordered neighbors of d other than b, giving (deg(d)−1)(deg(d)−2) choices. Because the graph is a tree, none of the neighbors chosen at one endpoint can equal a neighbor chosen at the other endpoint: that would create a triangle. Thus the two choices can be multiplied independently.
3. Sum this product for both orientations of every edge. In the example only b=2,d=4 can be the central directed edge. There are 3! choices of head and arms and 2! choices of feet, giving 12. Return zero factors immediately when an endpoint has too few neighbors.

Why it works

Every valid figure determines one directed edge from its chest to its waist. For this edge the falling factorials count every permitted assignment of the remaining roles exactly once. The tree property ensures all seven selected vertices are distinct and no forbidden overlap arises. Different directed edges or role assignments give different tuples, so summing the products counts exactly all figures.

Watch out. The roles are ordered; use falling factorials, not binomial coefficients. Count both edge orientations. Reduce products between factors to avoid overflow.

An independently written complete program with standard headers.

#include<iostream>
#include<utility>
#include<vector>
// Algorithm: Fix the directed central edge b→d.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>degree(n+1);
    vector<pair<int,int>>edges(n-1);
    for(auto&edge:edges){
        cin>>edge.first>>edge.second;
        ++degree[edge.first];
        ++degree[edge.second];
    }
    const long long mod=1000000007;
    auto choices=[&](int vertex,int count){
        if(degree[vertex]-1<count){
            return 0LL;
        }
        long long answer=1;
        for(int i=1;i<=count;++i){
            answer=answer*(degree[vertex]-i)%mod;
        }
        return answer;
    };
    long long answer=0;
    for(auto edge:edges){
        answer=(answer+choices(edge.first,3)*choices(edge.second,2))%mod;
        answer=(answer+choices(edge.second,3)*choices(edge.first,2))%mod;
    }
    cout<<answer<<'\n';
}