codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

690F1.md (1648B)


      1 Source: https://codeforces.com/problemset/problem/690/F1
      2 
      3 F1. Tree of Life (easy)
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Heidi has finally found the mythical Tree of Life – a legendary combinatorial structure which is said to contain a prophecy crucially needed to defeat the undead armies.
     22 
     23 On the surface, the Tree of Life is just a regular undirected tree well-known from computer science. This means that it is a collection of *n* points (called vertices), some of which are connected using *n* - 1 line segments (edges) so that each pair of vertices is connected by a path (a sequence of one or more edges).
     24 
     25 To decipher the prophecy, Heidi needs to perform a number of steps. The first is counting the number of lifelines in the tree – these are paths of length 2, i.e., consisting of two edges. Help her!
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer *n* – the number of vertices in the tree (1 ≤ *n* ≤ 10000). The vertices are labeled with the numbers from 1 to *n*. Then *n* - 1 lines follow, each describing one edge using two space-separated numbers *a* *b* – the labels of the vertices connected by the edge (1 ≤ *a* < *b* ≤ *n*). It is guaranteed that the input represents a tree.
     30 
     31 Output
     32 
     33 Print one integer – the number of lifelines in the tree.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4  
     41 1 2  
     42 1 3  
     43 1 4
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 3
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 5  
     56 1 2  
     57 2 3  
     58 3 4  
     59 3 5
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 4
     66 ```
     67 
     68 Note
     69 
     70 In the second sample, there are four lifelines: paths between vertices 1 and 3, 2 and 4, 2 and 5, and 4 and 5.