# MAXTOPO - Editorial

Author: Sayantan Jana
Tester: Felipe Mota
Editorialist: Sayantan Jana

Easy-Medium

# PREREQUISITES:

DFS, Dynamic Programming

# PROBLEM:

Given a tree G with N nodes and N-1 undirected edges .

Among all nodes, you can pick a node u and give a direction to each edge in G in a way that node u is reachable from all the nodes in G, to obtain a digraph G’ . It can be proved that the digraph G’ is a Directed Acyclic Graph.

Find the node in G corresponding to whose pick the digraph G’ obtained has maximum or second maximum number of topological sort orderings . Also report the number of topological sort orderings modulo 10^9 + 7 corresponding to those nodes.

# QUICK EXPLANATION:

• The number of topological sort orderings corresponding to a node can be found through dynamic programming and DFS fixing the node as root. However the number is quite large to fit in allowed data types.
• However using a similar technique we use in rerooting trick, we can notice that the number of topological sort orderings for a root and its child obeys a simple ratio in terms of their subtree sizes,
\frac{toposorts_{child}}{toposorts_{root}} = \frac{subtree\_size_{child}}{N-subtree\_size_{child}}
• This leads to centroid being the node corresponding to maximum topological sort orderings. The child of centroid with the greatest subtree size corresponds to second maximum topological sort orderings. There can be multiple candidates, pick maximum of them.
• The number of topological sort orderings modulo 10^9 + 7 corresponding to those nodes can be found using dynamic programming and DFS fixing the node as root.

# EXPLANATION:

Each of the points in quick explanation is to be discussed in detail here.

Counting number of topological sort orderings corresponding to a given node

We solve the problem : Given an undirected and unrooted tree. We make it rooted by choosing a node as a root. Now we need to find the number of possible orderings of all the nodes in such a way that no ancestor of a node should appear before the node for all the nodes in the rooted tree.

If we solve this, we know the answer for number of topological sort orderings for a node.

Consider the tree in the sample :

For node 2 as the root, we can have the possible topological orderings: (3,4,1,2), (4,3,1,2), (3,1,4,2), (4,1,3,2), (1,3,4,2) and (1,4,3,2).

Before putting a node in the ordering, we need to put all the nodes in its subtree in the ordering. This is the subproblem that we need to solve, i.e., to solve the above problem for the subtree rooted at the children of the node.

Let us suppose we have solved the subproblem, i.e., we know the number of possible topological sort orderings for each of the subtrees rooted at the children of the node u, denoted by dp[child_1], dp[child_2]dp[child_c], where c is the number of children of node u.
We can hence find the number of orderings for the concerned subtree rooted at node u. We need to take care of the following points :

• The node u appears at end of ordering.
• The orderings for the subtrees for its children do not lose their relative order (i.e., if 2 nodes a and b appear strictly in the order ab in the ordering of any of the subtrees for its children, the 2 nodes stay in the same order ab in the ordering for node u) but can occur in combination with other orderings (i.e., if 2 nodes a and
b appear strictly in the order ab in the ordering of any of the subtrees for its children, similarly 2 nodes c and d appear strictly in the order cd in the ordering of any other of the subtrees for its children, they may occur as acbd, abcd, cabd or any other possible way in the ordering for node u such that the relative order that’s decided is not lost).

Hence we arrive at the following relation :

dp[u] = \prod_{i=1}^{c} dp[child_i] \cdot \frac{(subtree\_size_{u}-1)!}{\prod_{i=1}^{c} subtree\_size_{child_i}!}

Now that we know the relation, we can make a DFS from the root of the rooted tree to get the required answer for the node.

To solve subtask 1, we can make a DFS from each of the nodes and find the answer for each node. Notice that the count would not be large enough. After getting the count for each node, we can just pick the nodes corresponding to maximum and second maximum count.

Ratio between the number of topological sort orderings for a root and its child as the new root

Say we have found the number of topological sort orderings for a node u and now want to find the same for an adjacent node of u, which occurs as a child of u in the tree rooted at u.

Let node u have c children child_1, child_2child_c and we apply rerooting to make child_1 the new root to find number of topological sort orderings for a node child_1.

Let subtree size in the old rooted tree (i.e., the one root at u) be denoted by old\_ssize[] and the subtree size in the new rooted tree (i.e., the one root at child_1) be denoted by new\_ssize[].

toposorts_u = \prod_{i=1}^{c} dp[child_i] \cdot \frac{(N-1)!}{\prod_{i=1}^{c} old\_ssize[child_i]!}

On rerooting,

new\_ssize[u] = N-old\_ssize[child_1]
dp[u] = \prod_{i=2}^{c} dp[child_i] \cdot \frac{(N-old\_ssize[child_1]-1)!}{\prod_{i=2}^{c} old\_ssize[child_i]!}
toposorts_{child_1} = \frac{dp[child_1]}{(old\_ssize[child_1]-1)!} \cdot \frac{dp[u]*(N-1)!}{(N-old\_ssize[child_1])!}

Replace the expression for dp[u] in the above and try simplifying the expression thus obtained to somehow replace a cluster of terms by toposorts_u.

We then notice,

toposorts_{child_1} = toposorts_u \cdot \frac{old\_ssize[child_1]}{N-old\_ssize[child_1]}

and hence proved is the ratio stated in quick explanation section,

\frac{toposorts_{child}}{toposorts_{root}} = \frac{subtree\_size_{child}}{N-subtree\_size_{child}}

Centroid is the node corresponding to maximum number of orderings

Suppose we are at a node and we want to make a move from the node to one of its children corresponding to which the number of orderings are greater than that for the node.

The child will obey the condition that

\frac{subtree\_size_{child}}{N-subtree\_size_{child}} > 1

This is from the above relation.
This reduces to,

subtree\_size_{child} > N/2

If we keep on making a move like this, we will finally stop at a node which if treated as the root, will have the subtree sizes of each of its children \leq N/2. Hence the required node is the centroid of the tree. Getting the centroid, we can use a DFS and the above DP relation to find the number of orderings modulo 10^9 + 7. This is how we solve subtask 2.

Note that there could be 2 possible centroids in the tree, we choose the maximum between them.

Getting the second maximum

Using the above ratio, we found that centroid corresponds to maximum possible orderings. Further using the same ratio we can realise that whichever node is the contributor for 2-nd maximum needs to be immediately close to the centroid, i.e., be a child of the centroid and also which has the maximum subtree size.

Having maximum subtree size is directly reflected from the ratio, but why exactly the child with maximum subtree size and not any other node in the subtree of that child ? It is because the subtree size of child (let’s say v) can at most be N/2 (cannot be greater else the definition of centroid would be violated). Now any other node in the subtree of v can have at most N/2 - 1 nodes in its subtree and hence it cannot have greater number of orderings than v.

Note, here too we may have multiple candidates, so we need to pick the maximum among them. We can use a DFS and the above DP relation to find the second number of orderings modulo 10^9 + 7.

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

const int M = (1<<20)+5;
const int md = 1e9+7;

int sz[M],dp[M],fact[M],inv_fact[M],parent[M];
int n;

int pwr(int a,int n,int m)
{
int p = 1;
while(n)
{
if(n&1)
p = 1ll*p*a%m;
a = 1ll*a*a%m;
n >>= 1;
}
return p;
}

void gather_sizes(int u,int par)
{
sz[u] = 1;
parent[u] = par;
{
if(v == par) continue;
gather_sizes(v,u);
sz[u] += sz[v];
}
}

int get_max(int u)
{
int cur_root = u;
bool flag = true;
while(flag)
{
flag = false;
{
if(v == parent[cur_root]) continue;
if(2*sz[v]>n)
{
cur_root = v;
flag = true;
break;
}
}
}
{
if(v == parent[cur_root]) continue;
if(2*sz[v] == n && v>cur_root)
return v;
}
return cur_root;
}

int get_second_max(int u)
{
int mx = 0;
mx = max(mx,sz[v]);
int node = 0;
{
if(sz[v] == mx)
node = max(node,v);
}
return node;
}

int get_topo_count(int u,int par)
{
dp[u] = 1;
sz[u] = 1;
{
if(v == par) continue;
get_topo_count(v,u);
dp[u] = 1ll*dp[u]*dp[v]%md;
dp[u] = 1ll*dp[u]*inv_fact[sz[v]]%md;
sz[u] += sz[v];
}
dp[u] = 1ll*dp[u]*fact[sz[u]-1]%md;
return dp[u];
}

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

int L = 500000;
fact[0] = 1;
inv_fact[0] = 1;
for(int i=1;i<=L;++i)
{
fact[i] = 1ll*fact[i-1]*i%md;
inv_fact[i] = pwr(fact[i],md-2,md);
}

int testcases;
cin >> testcases;
while(testcases--)
{
int k;
cin >> n >> k;
for(int i=1;i<n;++i)
{
int u,v;
cin >> u >> v;
}

gather_sizes(1,0);
int max_node = get_max(1);
int max_count = get_topo_count(max_node,0);
int second_max_node = get_second_max(max_node);
int second_max_count = get_topo_count(second_max_node,0);

if(k == 1)
cout << max_node << " " << max_count << "\n";
else
cout << second_max_node << " " << second_max_count << "\n";

for(int i=1;i<=n;++i)
}
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
struct union_find {
vector<int> parent;
int n;
union_find(int n) : n(n) { clear(); }
inline void clear(){ parent.assign(n, -1); }
inline int find(int u){ return (parent[u] < 0) ? u : parent[u] = find(parent[u]); }
inline bool same(int u, int v){ return find(u) == find(v); }
inline bool join(int u, int v){
u = find(u);
v = find(v);
if (u != v){
if (parent[u] > parent[v])
swap(u, v);
parent[u] += parent[v];
parent[v] = u;
}
return u != v;
}
inline int size(int u){ return -parent[find(u)]; }
};
template<typename T = int, T mod = 1'000'000'007, typename U = long long>
struct umod{
T val;
umod(): val(0){}
umod(U x){ x %= mod; if(x < 0) x += mod; val = x;}
umod& operator += (umod oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
umod& operator -= (umod oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
umod& operator *= (umod oth){ val = ((U)val) * oth.val % mod; return *this; }
umod& operator /= (umod oth){ return *this *= oth.inverse(); }
umod& operator ^= (U oth){ return *this = pwr(*this, oth); }
umod operator + (umod oth) const { return umod(*this) += oth; }
umod operator - (umod oth) const { return umod(*this) -= oth; }
umod operator * (umod oth) const { return umod(*this) *= oth; }
umod operator / (umod oth) const { return umod(*this) /= oth; }
umod operator ^ (long long oth) const { return umod(*this) ^= oth; }
bool operator < (umod oth) const { return val < oth.val; }
bool operator > (umod oth) const { return val > oth.val; }
bool operator <= (umod oth) const { return val <= oth.val; }
bool operator >= (umod oth) const { return val >= oth.val; }
bool operator == (umod oth) const { return val == oth.val; }
bool operator != (umod oth) const { return val != oth.val; }
umod pwr(umod a, U b) const { umod r = 1; for(; b; a *= a, b >>= 1) if(b&1) r *= a; return r; }
umod inverse() const {
U a = val, b = mod, u = 1, v = 0;
while(b){
U t = a/b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if(u < 0)
u += mod;
return u;
}
};
using U = umod<>;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(t--){
int n = readIntSp(1, 5 * TEN(5));
union_find uf(n);
for(int i = 1; i < n; i++){
u--; v--;
assert(uf.join(u, v));
}
using ld = long double;
vector<pair<ld, int>> pts;
vector<int> sz(n);
function<void(int, int)> compute = [&](int u, int p){
sz[u] = 1;
if(v == p) continue;
compute(v, u);
sz[u] += sz[v];
}
};
compute(0, -1);
ld val_root = 0;
for(int i = 0; i < n; i++){
val_root += log(sz[i]);
}
function<void(int, int, ld)> fix = [&](int u, int p, ld val){
if(p != -1){
val -= log(sz[u]);
val += log(n - sz[u]);
}
pts.push_back({-val, u});
if(v == p) continue;
fix(v, u, val);
}
};
fix(0, -1, val_root);
sort(pts.rbegin(), pts.rend());
compute(pts[k - 1].second, -1);
U ans = 1;
for(int i = 1; i <= n; i++)
ans *= i;
for(int i = 0; i < n; i++)
ans /= sz[i];
cout << pts[k - 1].second + 1 << ' ' << ans.val << '\n';
}
return 0;
}

10 Likes

Why is the problem in beginner’s section?

15 Likes

Awesome problem! Doesn’t this code order all of the “number of orderings” in descending order? If this is proven, we could have a variant where 1 \le k \le N not just 1 or 2.

3 Likes

I was struggling for 100 points since I got the logic but getting difficulties in implementing it.
Got Partial Points.
Thanks for nice editorial.

3 Likes

My new favorite problem! The problemset was awesome, thanks problemsetters and coordinators!

5 Likes

in your solution u stored all values as %m so after using it u cant tell which one is highest or lowest
for ex: (78,79)%79 = (78,0).
i did that same approch after lot of time i finally got lol.

mine too nice problem

Hey, could you please once check lines 67, 76, 77, and 110? maybe you’ll get an idea of what I did. I assumed the root performance as 1 then I multiplied by the fraction by which it is changing and sorted by that long double array.

1 Like

how it got ac tho?
could you explain how did u calculated that pref array?
like how it works?

yeah, let us assume the “number of orderings” of the root is some k. Then the performance array will store the fraction by which some other node of the tree differs with k.
let’s say \{1,1\},\{2,0.5\},\{3,1.38\} then we can say that 1 is root and 2 has about 50% of the “number of orderings” as 1 and 3 has 1.38 times. so the maximum is 3.
This performance array is calculated when moving down the child (re-rooting the tree) and the values are propagated.

1 Like

[Insight] Number of Topological Orderings of a Directed Tree - Codeforces.
this blog is also helpful. this help me during the contest

6 Likes

i did the same bro for all 1<=k<=n, really nice trick to maintain ratios and sort according to ratios and map the modded answer to print the required answer. You people can see my submission

2 Likes

it helped me too, rigorous searching for dynamic rooting and topological sorting in tree led me there

1 Like

bro, surprisingly i did almost same step, maintained ratios during rerooting dfs.
my submissionmy submission

2 Likes

Solving this MAXTOPO problem made me very happy. Thanks for this problem

1 Like

link to partial solution can anybody tell where I got wrong for 10 points,cuz what I did was just brute forced the solution and still got no ac

It helped me too. I derived the formula to calculate the Toplogical sorting (TS) when we fix a node , but it includes the number of TS of it’s childs and we can’t even store the answer for large values ( in order to compare with other node TS ) so i thought this is not the right way , and moved on to other problems , at last i wanted to give it another try , googled if there was another way to calculate the TS , and stumbled upon this blog , and finally realized that , i missed to recognize that the formula can be simplified.

2 Likes

I used the idea in this blog post to solve it for K \in {1,2,3, \ldots, N}. The idea is that the number of topological orderings, if the root is v, can be simply expressed as \frac{N!}{\prod_{u=1}^N s^{(v)}_u}, where s^{(v)}_u is the size of the subtree rooted at u. To find the root with the maximum number of orderings, you just have to find the minimum of the product, i.e., \min_v \prod_{u=1}^N s^{(v)}_u. This product can be large but you can take the logarithm. See this solution. The sorting in line 56 is an overkill for K \in {1,2}, but then in the next line we can choose any K.

5 Likes

@peresz can you please tell why you have used log and why it is helpful in this question.
And yes it was very awesome to come with that formula. Can you please tell, how you get the expression of number of topological orderings . observation or any theoretical ??

Good editorial. Nice Explanation.
Coincidentally, my approach is 80% similiar to editorial approach