TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P7938
  • Problem
  • P7938借鉴题解
    Limits : Time Limit : - MS   Memory Limit : 32768 KB
    Judgment Tips : 1s,32MB
    Description

    题解告诉我们,这道题答案在一棵 \(n\) 个节点的树上。
    定义 \(f(l,r)\) 表示让编号在区间 \([l,r]\) 内所有点连通需要的最少边数,答案就是

    \[ \sum_{l=1}^n \sum_{r=l}^n f(l,r) \]

    题解给了代码,但你一看就知道时间复杂度不对,那份代码必然TLE。
    于是你放弃了借鉴题解的打算,下定决心自己写一份标程。

    Input Format

    第一行一个整数 \(n\) ,接下来 \(n-1\) 行每行两个整数 \(x,y\) 表示一条边。

    Output Format

    一个整数答案。

    Sample Input

    4
    1 4
    1 3
    2 4

    Sample Output

    16

    Hint

    样例1

    样例输入

    4
    1 4
    1 3
    2 4
    

    样例输出

    16
    

    数据范围

    对于全部测试数据, $1\leq n\leq 10^5$ , $1\leq x,y\leq n$ 。

    20% n<=10
    40% n<=300
    60% n<=3000
    另外20% 一条链
    100% n<=100000