give solution in cpp D. Reachability and Tree tim...

Analysis

We need to orient the edges of a tree on $n$ vertices so that the total number of good pairs

$$\#\{(u,v)\mid u\ne v,\ \text{there is a directed path from }u\to v\}$$

is exactly $n$. A little thought shows

1. Every edge, once oriented, contributes at least one good pair (its two endpoints).
2. Every directed path of length ≥2 contributes extra good pairs (one for each “hop-over”).
3. Hence to get exactly $n$ good pairs from $n-1$ edges, we must have exactly one extra good pair beyond the $n-1$ contributed by the edges themselves. Equivalently: exactly one directed path of length 2, and no longer directed paths anywhere.

In a tree, a directed path of length 2 can only happen when a vertex $v$ has exactly one incoming edge and exactly one outgoing edge (so the two edges “chain” through $v$). If we tried to make that happen at a vertex of degree $\ge3$, its other incident edges would create additional length-2 paths and hence too many good pairs. Conversely, if the tree has a vertex of degree exactly 2, we can use that vertex as the unique “chain” node:

• Let $v$ be any vertex of degree 2, with neighbors $a,b$.
• Orient the two edges on that chain as $$a\;\to\;v\;\to\;b,$$

which creates exactly one extra good pair $a\to b$.

• The rest of the tree falls into two components (one containing $a$, one containing $b$) once $v$ is removed. In each component we must orient no two edges consecutively in the same direction. A neat way to do this in any bipartite graph (and our component is a tree, hence bipartite) is:

1. Two-color the component (say color 0/1).
2. Orient every edge from color 0 to color 1.

Since every path of length 2 in a bipartition alternates 0→1→0 or 1→0→1, one of those hops is always against the “0→1” rule, so you can never get two edges in the same direction. In particular there are no further length-2 directed paths in those components.

Putting that together:

1. If $n=2$ or there is no vertex of degree 2, answer NO.
2. Otherwise choose a degree-2 vertex $v$ with neighbors $a,b$.

• Orient $a\to v$ and $v\to b$.
• Remove $v$, run two BFS’s (one from $a$ with color 0, one from $b$ with color 1) to color each component 0/1.
• Orient every remaining edge from color 0 to color 1.
• You get exactly $n-1$ base pairs plus one extra from $a\to v\to b$, total $n$.

The whole thing runs in $O(n)$ per test, which is fine for $\sum n\le2\!\times\!10^5$.

---

cpp
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<vector<int>> adj(n+1);
        vector<pii> edges(n-1);
        for(int i = 0; i < n-1; i++){
            int u,v;
            cin >> u >> v;
            edges[i] = {u,v};
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // n=2 is impossible (only 1 reachable pair always)
        if(n == 2){
            cout << "NO\n";
            continue;
        }
        // find a vertex of degree exactly 2
        int chainV = -1;
        for(int i = 1; i <= n; i++){
            if(adj[i].size() == 2){
                chainV = i;
                break;
            }
        }
        if(chainV == -1){
            // no degree-2 vertex => can't create exactly one length-2 chain
            cout << "NO\n";
            continue;
        }

        // we will build our answer edges here
        vector<pii> ans;
        ans.reserve(n-1);

        // pick the two neighbors of chainV
        int a = adj[chainV][0];
        int b = adj[chainV][1];

        // 1) orient the unique chain a -> chainV -> b
        ans.emplace_back(a, chainV);
        ans.emplace_back(chainV, b);

        // prepare to 2-color the two components when chainV is removed
        vector<int> side(n+1, -1);
        // in the 'a' component we color a with 0
        // in the 'b' component we color b with 1
        side[a] = 0;
        side[b] = 1;

        // BFS from 'a' skipping chainV
        {
            queue<int> q;
            q.push(a);
            while(!q.empty()){
                int u = q.front(); q.pop();
                for(int w: adj[u]){
                    if(w == chainV || side[w] != -1) continue;
                    side[w] = side[u] ^ 1;
                    q.push(w);
                }
            }
        }
        // BFS from 'b' skipping chainV
        {
            queue<int> q;
            q.push(b);
            while(!q.empty()){
                int u = q.front(); q.pop();
                for(int w: adj[u]){
                    if(w == chainV || side[w] != -1) continue;
                    side[w] = side[u] ^ 1;
                    q.push(w);
                }
            }
        }

        // we already handled the two chain edges; now
        // orient every other edge from color 0 -> color 1
        auto norm = [&](int x,int y){
            if(x>y) swap(x,y);
            return make_pair(x,y);
        };
        auto c1 = norm(a, chainV);
        auto c2 = norm(b, chainV);

        for(auto &e: edges){
            int u = e.first, v = e.second;
            auto nm = norm(u,v);
            if(nm == c1 || nm == c2) 
                continue;  // skip the two chain edges
            // orient from side==0 to side==1
            if(side[u] == 0 && side[v] == 1){
                ans.emplace_back(u,v);
            } else {
                ans.emplace_back(v,u);
            }
        }

        // sanity: we must have exactly n-1 oriented edges
        assert((int)ans.size() == n-1);

        cout << "YES\n";
        for(auto &p: ans){
            cout << p.first << " " << p.second << "\n";
        }
    }

    return 0;
}

Explanation of Key Steps

1. Why degree-2?
   Only a vertex of degree 2 can host exactly one “incoming + outgoing” pair without spawning extra length-2 paths on its other edges.

2. Creating the single length-2 path
   We pick the two edges adjacent to that degree-2 vertex $v$, say $(a,v)$ and $(v,b)$, and orient them $a\to v\to b$. This single length-2 path contributes exactly one extra good pair $(a,b)$ beyond the $n-1$ from the edges.

3. Avoiding any other chains
   Removing $v$ splits the tree into two pieces (one on $a$’s side, one on $b$’s side). In each component we 2-color the vertices (it’s a tree, hence bipartite) and then orient every edge from color 0➝color 1. This ensures that no two edges can line up in the same direction, so there are no other directed paths of length ≥2.

Overall the result is exactly $n$ good pairs, as required.

Below is an $O(M\log M)$-precompute + $O(1)$ –per query solution, where $M=5\times10^5$. We build two DP tables:

1. dpNodes[f] = the minimum number of nodes in a rooted subtree (with its root’s parent fixed green) whose “$A$”–value is exactly $f$, where

$$A_v \;=\;\sum_{c\in\{g,b,y\}}\;\prod_{u\in\text{children}(v)}A_u(c)$$

and one shows that $A_v$ is always odd and that these $A_v$ are exactly the building‐blocks of the global count.

2. dpRoot[m] = the minimum total number of vertices in a full tree whose total number of beautiful colorings is exactly $m$. One proves that at the global root (which must be green) the total count factors as

$$m \;=\;\prod_{i=1}^k A_{v_i},$$

where the $v_i$ are its children, so

$$\text{nodes}=1+\sum_i\bigl(\text{size of subtree at }v_i\bigr) \;=\;1+\sum_i dpNodes[A_{v_i}].$$

Hence we do one final multiplicative DP over the divisors of $m$ to get the optimum split at the root.

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 500000;
const int INF = 1000000000;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Precompute divisors for all n<=M
    static vector<int> divs[M+1];
    for(int d = 1; d <= M; d += 2){           // only odd divisors matter, but we can do all
        for(int x = d; x <= M; x += d){
            divs[x].push_back(d);
        }
    }

    // 2) dpNodes[f] = min size of a subtree (excluding the global root)
    //    whose A-value = f.  We only care about odd f.
    static int dpNodes[M+1], D[M+1];
    // D[g] = minimal sum of dpNodes[fi] over a factorization g = ∏ fi  (all fi odd>1)
    //           (i.e. best way to break g into children at an *internal* node)
    memset(dpNodes, 0x3f, sizeof dpNodes);
    memset(D,        0x3f, sizeof D);
    dpNodes[1] = 0;   // no nodes needed to realize A=1 (empty product)
    D[1]       = 0;   // to factor 1 you pick nothing

    // Build up dpNodes in increasing order of f=3,5,7,...,M
    for(int f = 3; f <= M; f += 2){
        int g = f - 2;   // g = product of child A-values

        // compute D[g] = min_{d|g, d>1} ( dpNodes[d] + D[g/d] )
        if(g > 1){
            int best = INF;
            for(int d: divs[g]){
                if(d == 1) continue;
                best = min(best, dpNodes[d] + D[g/d]);
            }
            D[g] = best;
        }
        // start with the “path”‐shape cost
        dpNodes[f] = (f - 1) / 2;
        // or use an internal node giving A = g+2
        // cost = 1 (the internal node) + D[g]
        dpNodes[f] = min(dpNodes[f], 1 + D[g]);
    }

    // 3) dpRoot[m] = min #vertices in a full tree with exactly m colorings
    //    Root must be green ⇒ m = ∏ A[v_i].  We pay 1 for the root plus
    //    dpNodes[A[v_i]] for each child‐subtree.
    static int dpRoot[M+1];
    for(int i = 0; i <= M; i++) dpRoot[i] = INF;
    dpRoot[1] = 1;   // only the root, 1 beautiful coloring

    // fill in for odd m ≥3:
    for(int m = 3; m <= M; m += 2){
        // one‐child decomposition: root→subtree with A=m
        if(dpNodes[m] < INF)
            dpRoot[m] = 1 + dpNodes[m];

        // try splitting m = f * (m/f)
        for(int f: divs[m]){
            if(f == 1 || f == m) continue;
            dpRoot[m] = min(dpRoot[m],
                             dpRoot[m/f] + dpNodes[f]);
        }
    }

    // 4) answer queries
    int T;
    cin >> T;
    while(T--){
        int m;
        cin >> m;
        if(m == 1){
            cout << 1 << "\n";
        } else if((m & 1) == 0){
            cout << -1 << "\n";
        } else {
            int ans = dpRoot[m];
            if(ans >= INF) ans = -1;
            cout << ans << "\n";
        }
    }
    return 0;
}

Explanation of the Key Steps

1. Local DP for subtrees
   We show that for any node $v$ whose parent is fixed green, its contribution

   $$A_v \;=\;\bigl(\prod_{u\in\mathrm{ch}(v)}A_u\bigr)\;+\;2$$

   produces exactly all odd values $\ge3$. We let

   dpNodes[f] = \min\{\text{#nodes of a subtree rooted at }v : A_v = f\}.

   One easily sees that the “path” shape gives $f=2s+1$ with $s$ nodes, and any multi‐child shape gives $f = g+2$ where $g=\prod A_u$. Factoring $g$ into its child-contributions is itself a knapsack on multiplication, which we solve via

   $$D[g] = \min_{d\mid g,\;d>1}\!\bigl(dpNodes[d] + D[g/d]\bigr), \quad dpNodes[f] = \min\Bigl(\tfrac{f-1}{2},\,1 + D[f-2]\Bigr).$$

2. Global DP at the root
   Since the global root must be green, the total count of beautiful colorings factors as

   $$m \;=\;\prod_{i=1}^k A_{v_i},$$

   where the $v_i$ are its immediate children. The total vertex‐count is $1+\sum_i (\text{size of subtree at }v_i)$. Hence

   $$dpRoot[m] = 1 + \min_{\substack{f|m\\1<f\le m}} \bigl(dpRoot[m/f]+dpNodes[f]\bigr), \quad dpRoot[1]=1.$$

   Finally we answer each query in $O(\tau(m))$, where $\tau(m)$ is the divisor‐count, an acceptable total cost over all $m\le5\cdot10^5$.

This runs in about $O(M\log M)$ to precompute and then $O(1)$ per test.