Hello coders, today we are going to solve Tree of Trees Codechef Solution whose Problem Code is TREETREE.
Tree of Trees Codechef Solution
Problem
You are given N edge-weighted trees T1, T2,…..TN having M1, M2 ….. MN nodes respectively. You also have an array A of N-1 positive integers.
You need to connect these NN trees using N-1N−1 edges such that each of these edges have weights equal to A_iAi for some i \in [1,N-1]i∈[1,N−1] and each of the A_iAi must be used exactly once. Note that after connecting these edges, a single large tree TT will form consisting of (M_1+M_2+\ldots+M_N)(M1+M2+…+MN) nodes. Find the minimum possible sum of distances between each pair of nodes in the final tree TT.
Since this value can be large, output the value mod 998244353998244353.
Input Format
- The first line of input will contain a single integer NN, denoting the number of trees.
- Then, you are given the NN trees. The description of each tree is as follows:
- The first line contains the integer M_iMi (1 \le i \le N)(1≤i≤N), the number of nodes in ii-th tree.
- The next M_i-1Mi−1 lines describe the edges of the ii-th tree. The jj-th of these M_i-1Mi−1 lines contains 33 space-separated integers u_{ij}, v_{ij}uij,vij and w_{ij}wij, describing that there is an edge of weight w_{ij}wij connecting the nodes u_{ij}uij and v_{ij}vij in tree T_iTi.
- The final line contains N-1N−1 space-separated integers, A_1, A_2,\ldots,A_{N-1}A1,A2,…,AN−1.
Output Format
For each test case, output on a new line the minimum sum of distances between each pair of nodes in tree TT, modulo 998244353998244353.
Constraints
- 2 \leq N \leq 10^42≤N≤104
- 1 \leq M_i \leq 5\cdot 10^41≤Mi≤5⋅104
- 1 \leq u_{ij}, v_{ij} \leq M_i1≤uij,vij≤Mi
- 1 \leq w_{ij} \leq 10^81≤wij≤108
- 1 \leq A_i \leq 10^81≤Ai≤108
- The sum (M_1+M_2+\ldots +M_N)(M1+M2+…+MN) does not exceed 10^5105.
Subtasks
- Subtask 1 (30 points): N = 2N=2
- Subtask 2 (70 points): Original constraints.
Sample 1:
Input
2 3 1 2 1 2 3 3 4 1 2 2 1 3 1 1 4 3 1
Output
72
Explanation:
An optimal solution for the given test case looks as follows:
Tree of Trees Codechef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mx 200000
#define mp make_pair
#define pii pair<ll,ll>
#define fs first
#define sc second
#define mx 200000
vector<int>vc[mx],cost[mx];
bool deg[mx];
int aged[mx];
void clr(int n)
{
for(int i=1; i<=n; i++)
{
deg[i]=0;
vc[i].clear();
cost[i].clear();
}
}
int find(int n)
{
for(int i=1; i<=n; i++)
{
if(deg[i]==0)
return i;
}
assert(0);
}
ll base[]= {103,10007},mod[]= {784568360, 820925358};
ll base2[]= {137,277},mod2[]= {1000000007,1000000009};
ll base3[]= {701,41},mod3[]= {998244353,1012924417};
ll day[2][2][2],age[2][120][2],brac[2][2];
set<pii>s;
pii dfs(int v,bool x)
{
ll sum[2];
sum[0]=0;
sum[1]=0;
for(int i=0; i<vc[v].size(); i++)
{
int w=vc[v][i];
pii ps=dfs(w,x);
int c=cost[v][i];
ll val[2];
val[0]=ps.fs;
val[1]=ps.sc;
for(int j=0; j<2; j++)
{
val[j]*=base[j];
val[j]%=mod[j];
}
for(int j=0; j<2; j++)
{
val[j]+=(day[j][c][0]+day[j][c][1])%mod2[j];
val[j]%=mod2[j];
sum[j]+=val[j];
if(sum[j]>=mod2[j])
sum[j]%=mod2[j];
}
}
for(int j=0; j<2; j++)
{
sum[j]*=base2[j];
sum[j]%=mod2[j];
sum[j]+=(brac[j][0]+brac[j][1])%mod[j];
sum[j]%=mod[j];
int d=aged[v];
sum[j]+=(age[j][d][0]+age[j][d][1])%mod3[j];
sum[j]%=mod3[j];
}
if(x)
s.insert(mp(sum[0],sum[1]));
return mp(sum[0],sum[1]);
}
#define pb push_back
int main()
{
srand(time(NULL));
int i,j,k,l,m,n;
for(int i=0; i<101; i++)
{
for(int j=0; j<=1; j++)
{
age[j][i][0]=rand();
age[j][i][1]=rand();
}
}
for(int i=0; i<2; i++)
{
brac[i][0]=rand();
brac[i][1]=rand();
}
for(int i=0; i<2; i++)
{
for(int j=0; j<2; j++)
{
for(int k=0; k<2; k++)
{
day[i][j][k]=rand();
}
}
}
cin>>n;
char str[5];
for(int i=1; i<=n; i++)
{
scanf("%d",&aged[i]);
}
for(int i=1; i<n; i++)
{
scanf("%d%d%s",&l,&k,str);
vc[l].pb(k);
deg[k]=1;
int c=0;
if(str[0]=='E')
c=1;
cost[l].pb(c);
}
int root=find(n);
dfs(root,1);
int Q;
cin>>Q;
while(Q--)
{
scanf("%d",&n);
clr(n);
for(int i=1; i<=n; i++)
{
scanf("%d",&aged[i]);
}
for(int i=1; i<n; i++)
{
scanf("%d%d%s",&l,&k,str);
vc[l].pb(k);
deg[k]=1;
int c=0;
if(str[0]=='E')
c=1;
cost[l].pb(c);
}
int root2=find(n);
pii rs= dfs(root2,0);
if(s.find(rs)!=s.end())printf("YES\n");
else printf("NO\n");
}
}
Tree of Trees Codechef Solution in JAVA
Coming soon
Tree of Trees Codechef Solution in Python
Coming soon
Disclaimer: The above Problem (Tree of Trees ) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
