Maximum and Minimum

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JULY19/hindi/MXMN.pdf), [Bengali](http://www.codechef.com/download/translated/JULY19/bengali/MXMN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JULY19/mandarin/MXMN.pdf), [Russian](http://www.codechef.com/download/translated/JULY19/russian/MXMN.pdf) and [Vietnamese](http://www.codechef.com/download/translated/JULY19/vietnamese/MXMN.pdf) as well. Chef loves graphs. To express his love, he defines a function $f(G, x, y)$ for an undirected connected graph $G$ with weighted edges and two of its vertices $x$, $y$. $f(G, x, y)$ is defined as the minimum of weights of all paths in $G$ between the vertices $x$ and $y$, where the weight of a path is the maximum of weights of edges in this path. Chef has two connected graphs $G_1$ and $G_2$. Each of these graphs has $N$ vertices (labelled $1$ through $N$) and $M$ edges. Calculate $$S = \sum_{i=1}^{N1} \sum_{j=i+1}^N f(G_1, i, j) \cdot f(G_2, i, j)$$ modulo $998,244,353$. ### Input  The first line of the input contains two spaceseparated integers $N$ and $M$.  $M$ lines follow. Each of these lines contains three spaceseparated integers $u$, $v$ and $w$ denoting that vertices $u$ and $v$ in $G_1$ are connected by an edge with weight $w$.  $M$ more lines follow. Each of these lines contains three spaceseparated integers $u$, $v$ and $w$ denoting that vertices $u$ and $v$ in $G_2$ are connected by an edge with weight $w$. ### Output Print a single line containing one integer — the sum $S$ modulo $998,244,353$. ### Constraints  $1 \le N \le 10^5$  $M = 2N$  $1 \le u, v \le N$  $1 \le w \le 10^8$  $G_1$ and $G_2$ are connected graphs ### Subtasks **Subtask #1 (20 points):** $N = 2,000$ **Subtask #2 (30 points):**  $N = 10^5$  $G_1$ and $G_2$ are identical graphs **Subtask #3 (50 points):** original constraints ### Example Input ``` 3 6 1 2 3 2 3 1 3 1 2 1 2 4 2 3 5 3 1 6 1 2 2 2 3 1 3 1 3 1 2 5 2 3 4 3 1 6 ``` ### Example Output ``` 9 ```Author:  nqiiii 
Editorial  https://discuss.codechef.com/problems/MXMN 
Tags  auxiliarytree, centroiddecomp, hard, july19, nqiiii, trees 
Date Added:  14062019 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions