GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday, 4 September 2022

[Solution] Imitating the Key Tree Codeforces Solution



I. Imitating the Key Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pak Chanek has a tree called the key tree. This tree consists of N vertices and N1 edges. The edges of the tree are numbered from 1 to N1 with edge i connecting vertices Ui and Vi. Initially, each edge of the key tree does not have a weight.

Formally, a path with length k in a graph is a sequence [v1,e1,v2,e2,v3,e3,,vk,ek,vk+1] such that:

  • For each ivi is a vertex and ei is an edge.
  • For each iei connects vertices vi and vi+1.

A circuit is a path that starts and ends on the same vertex.

A path in a graph is said to be simple if and only if the path does not use the same edge more than once. Note that a simple path can use the same vertex more than once.

The cost of a simple path in a weighted graph is defined as the maximum weight of all edges it traverses.

Count the number of distinct undirected weighted graphs that satisfy the following conditions:

  • The graph has N vertices and 2N2 edges.
  • For each pair of different vertices (x,y), there exists a simple circuit that goes through vertices x and y in the graph.
  • The weight of each edge in the graph is an integer between 1 and 2N2 inclusive. Each edge has distinct weights.
  • The graph is formed in a way such that there is a way to assign a weight Wi to each edge i in the key tree that satisfies the following conditions:
    • For each pair of edges (i,j), if i<j, then Wi<Wj.
    • For each pair of different vertex indices (x,y), the cost of the only simple path from vertex x to y in the key tree is equal to the minimum cost of a simple circuit that goes through vertices x and y in the graph.
  • Note that the graph is allowed to have multi-edges, but is not allowed to have self-loops.

Solution Click Below:-  ðŸ‘‰CLICK HERE👈
👇👇👇👇👇

Print the answer modulo 998244353.

Two graphs are considered distinct if and only if there exists a triple (a,b,c) such that there exists an edge that connects vertices a and b with weight c in one graph, but not in the other.

Input

The first line contains a single integer N (2N105) — the number of vertices in the key tree.

The i-th of the next N1 lines contains two integers Ui and Vi (1Ui,ViN) — an edge connecting vertices Ui and Vi. The graph in the input is a tree.

Output

An integer representing the number of distinct undirected weighted graphs that satisfy the conditions of the problem modulo 998244353.

No comments:

Post a Comment