Language: C++

 cities numbered 1 through N, which are connected by N−1 bidirectional roads. In terms of graph theory, there is a unique simple path connecting every pair of cities. That is, the N cities form a tree. Besides, if we view city 1 as the root of this tree, the tree will be a full binary tree (a tree is a full binary tree if and only if every non-leaf vertex in the tree has exactly two children). Roads are numbered 1 through N−1. The i-th road connects city i+1 and city ai. When you pass through road i, the toll you should pay is vi (if vi is 0

, it indicates the road does not require a toll).

A company in city 1

will give each employee a family travel and cover a large part of the tolls incurred. Each employee can design the travel by themselves. That is, which cities he/she wants to visit in each day and which city to stay at each night. However, there are some constraints. More details are as follows:

The travel must start and end at city 1
. If there are m leaves in the tree formed by the cities, then the number of days in the travel must be m+1

. At the end of each day, except for the last day, the employee must stay at some hotel in a leaf city. During the whole travel, the employee must stay at all leaf cities exactly once.

During the whole travel, all roads of the country must be passed through exactly twice.

The amount that the employee must pay for tolls by him/herself is the maximum total toll incurred in a single day during the travel, except the first day and the last day. The remaining tolls will be covered by the company.

Shik, as an employee of this company, has only one hope for his travel. He hopes that the amount he must pay for tolls by himself will be as small as possible. Please help Shik to design the travel which satisfies his hope.
Constraints

2<N<131,072

1≤ai≤i for all i
0≤vi≤131,072
vi

is an integer
The given tree is a full binary tree
Input

The input is given from Standard Input in the following format:

N
a1 v1
a2 v2
:
aN−1 vN−1

    1
    2
    3
    4
    5

Output

Print an integer denoting the minimum amount Shik must pay by himself for tolls incurred during the travel.
Sample Input 1

7
1 1
1 1
2 1
2 1
3 1
3 1

    1
    2
    3
    4
    5
    6
    7

Sample Output 1

4

    1

There are 4 leaves in the tree formed by the cities (cities 4, 5, 6, and 7), so the travel must be 5 days long. There are 4!=24 possible arrangements of the leaf cities to stay during the travel, but some of them are invalid. For example, (4,5,6,7) and (6,7,5,4) are valid orders, but (5,6,7,4) is invalid because the route passes 4 times through the road connecting city 1 and city 2. The figure below shows the routes of the travel for these arrangements.

pic1
For all valid orders, day 3 is the day with the maximum total incurred toll of 4, passing through 4 roads.
Sample Input 2

9
1 2
1 2
3 2
3 2
5 2
5 2
7 2
7 2

    1
    2
    3
    4
    5
    6
    7
    8
    9

Sample Output 2

6

    1

The following figure shows the route of the travel for one possible arrangement of the stayed cities for the solution. Note that the tolls incurred in the first day and the last day are always covered by the company.

pic2
Sample Input 3

15
1 2
1 5
3 3
4 3
4 3
6 5
5 4
5 3
6 3
3 2
11 5
11 3
13 2
13 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

Sample Output 3

15

    1

Sample Input 4

3
1 0
1 0

    1
    2
    3

Sample Output 4

0

    1

想到方法却不会证明复杂度系列……
神题一道.jpg

思路:
考虑先二分答案，那么现在问题变成了判定合法性。
只要咱们可以构建出一个合法的，且除了第一条和最后一条路径外，没有一条路径边权超过当前二分答案的方案，即可说明其合法性。

那么，考虑如何证明这样方案的存在性:
由于一条边经过次数不超过2，可以很容易发现这样的事实:一旦你进入了某棵子树，只有走完了里面的所有叶子结点，才可以出去。

那么考虑维护一种二元组，形如(a,b)u
，代表以当前节点u为根节点的子树中，入边的长度为a，出边的长度为b

，且这棵子树内部存在至少一条合法路径满足权值小于等于二分的答案，的一种方案。

于是每个节点均可以使用vector
存储若干个方案，可以很轻松的转移:
(a,b)u=(a,i)ch[0]+(j,b)ch[1](i+j<=ans)
注意二元组的 a,b

可以互换。

然而可以发现根节点的方案数将会等于爆搜搜到的方案数。
考虑优化状态数，可以发现对于每个a
，只会需求最小的一个合法的b配对，同理b

也是这样。

那么，分割线下为本蒟蒻未想到的部分……

考虑启发式合并，可以发现statecount(u)<=2∗min(statecount(ch[0]),statecount(ch[1]))
，因为咱们总是可以选取较小的那一边，此时每个a和b最多只会贡献一种新方案。
于是状态数变成O(nlogn)，复杂度是十分正确的O(nlognlogv)

。

于是做完了~

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'|| ch>'9')ch=getchar();
    while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
    return x;
}

typedef long long ll;
typedef pair<ll,ll> pr;
typedef vector<pr> vec;
#define x first
#define y second
const int N=131100;

int n,fa[N];
vec g[N],f[N];
ll mid,mv[N];

inline bool cmpx(pr a,pr b){return a.x<b.x;}
inline bool cmpy(pr a,pr b){return a.y<b.y;}

inline void work(vec &ls,vec &rs,vec &f)
{
    if(ls.size()>rs.size())swap(ls,rs);
    int el=ls.size(),er=rs.size();

    sort(ls.begin(),ls.end(),cmpy);
    sort(rs.begin(),rs.end(),cmpx);

    mv[0]=rs[0].y;
    for(int i=1;i<er;i++)
        mv[i]=min(mv[i-1],rs[i].y);

    for(int i=0,j=er-1;i<el;i++)
    {
        while(j>=0 && ls[i].y+rs[j].x>mid)j--;
        if(j>=0)f.push_back(pr(ls[i].x,mv[j]));
    }

    sort(ls.begin(),ls.end(),cmpx);
    sort(rs.begin(),rs.end(),cmpy);
    mv[0]=rs[0].x;
    for(int i=1;i<er;i++)
        mv[i]=min(mv[i-1],rs[i].x);

    for(int i=0,j=er-1;i<el;i++)
    {
        while(j>=0 && ls[i].x+rs[j].y>mid)j--;
        if(j>=0)f.push_back(pr(mv[j],ls[i].y));
    }
}

inline void dfs(int u)
{
    if(!f[u].empty())f[u].clear();
    if(g[u].empty())
    {
        f[u].push_back(pr(0,0));
        return;
    }

    for(int i=0,e=g[u].size();i<e;i++)
        dfs(g[u][i].x);

    vec &ls=f[g[u][0].x];
    for(int i=0,e=ls.size(),c=g[u][0].y;i<e;i++)
        ls[i].x+=c,ls[i].y+=c;
    vec &rs=f[g[u][1].x];
    for(int i=0,e=rs.size(),c=g[u][1].y;i<e;i++)
        rs[i].x+=c,rs[i].y+=c;

    work(ls,rs,f[u]);
    ls.clear();
    rs.clear();
}

int main()
{
    n=read();
    for(int i=2,a;i<=n;i++)
    {
        fa[i]=read();
        g[fa[i]].push_back(pr(i,read()));
    }

    ll l=0,r=1e10,ans=1e10;
    while(l<=r)
    {
        mid=l+r>>1;
        dfs(1);
        if(f[1].empty())
            l=mid+1;
        else
            r=mid-1,ans=mid;
    }

    printf("%lld\n",ans);
    return 0;
}

Compiler output:
a.cc:1:54: error: extended character − is not valid in an identifier
    1 |  cities numbered 1 through N, which are connected by N−1 bidirectional roads. In terms of graph theory, there is a unique simple path connecting every pair of cities. That is, the N cities form a tree. Besides, if we view city 1 as the root of this tree, the tree will be a full binary tree (a tree is a full binary tree if and only if every non-leaf vertex in the tree has exactly two children). Roads are numbered 1 through N−1. The i-th road connects city i+1 and city ai. When you pass through road i, the toll you should pay is vi (if vi is 0
      |                                                      ^
a.cc:1:427: error: extended character − is not valid in an identifier
    1 |  cities numbered 1 through N, which are connected by N−1 bidirectional roads. In terms of graph theory, there is a unique simple path connecting every pair of cities. That is, the N cities form a tree. Besides, if we view city 1 as the root of this tree, the tree will be a full binary tree (a tree is a full binary tree if and only if every non-leaf vertex in the tree has exactly two children). Roads are numbered 1 through N−1. The i-th road connects city i+1 and city ai. When you pass through road i, the toll you should pay is vi (if vi is 0
      |                                                                                                                                                                                                                                                                                                                                                                                                                                           ^
a.cc:23:1: error: extended character ≤ is not valid in an identifier
   23 | 1≤ai≤i for all i
      | ^
a.cc:23:1: error: extended character ≤ is not valid in an identifier
a.cc:24:1: error: extended character ≤ is not valid in an identifier
   24 | 0≤vi≤131,072
      | ^
a.cc:24:1: error: extended character ≤ is not valid in an identifier
a.cc:37:1: error: extended character − is not valid in an identifier
   37 | aN−1 vN−1
      | ^
a.cc:37:6: error: extended character − is not valid in an identifier
   37 | aN−1 vN−1
      |      ^
a.cc:163:1: error: extended character … is not valid in an identifier
  163 | 想到方法却不会证明复杂度系列……
      | ^
a.cc:163:1: error: extended character … is not valid in an identifier
a.cc:167:1: error: extended character 。 is not valid in an identifier
  167 | 考虑先二分答案，那么现在问题变成了判定合法性。
      | ^
a.cc:168:1: error: extended character 。 is not valid in an identifier
  168 | 只要咱们可以构建出一个合法的，且除了第一条和最后一条路径外，没有一条路径边权超过当前二分答案的方案，即可说明其合法性。
      | ^
a.cc:171:53: error: extended character 。 is not valid in an identifier
  171 | 由于一条边经过次数不超过2，可以很容易发现这样的事实:一旦你进入了某棵子树，只有走完了里面的所有叶子结点，才可以出去。
      |                                                     ^
a.cc:176:1: error: extended character 。 is not valid in an identifier
  176 | ，且这棵子树内部存在至少一条合法路径满足权值小于等于二分的答案，的一种方案。
      | ^
a.cc:183:1: error: extended character 。 is not valid in an identifier
  183 | 可以互换。
      | ^
a.cc:185:1: error: extended character 。 is not valid in an identifier
  185 | 然而可以发现根节点的方案数将会等于爆搜搜到的方案数。
      | ^
a.cc:189:1: error: extended character 。 is not valid in an identifier
  189 | 也是这样。
      | ^
a.cc:191:1: error: extended character … is not valid in an identifier
  191 | 那么，分割线下为本蒟蒻未想到的部分……
      | ^
a.cc:191:1: error: extended character … is not valid in an identifier
a.cc:193:40: error: extended character ∗ is not valid in an identifier
  193 | 考虑启发式合并，可以发现statecount(u)<=2∗min(statecount(ch[0]),statecount(ch[1]))
      |                                        ^
a.cc:194:1: error: extended character 。 is not valid in an identifier
  194 | ，因为咱们总是可以选取较小的那一边，此时每个a和b最多只会贡献一种新方案。
      | ^
a.cc:197:1: error: extended character 。 is not valid in an identifier
  197 | 。
      | ^
a.cc:1:2: error: 'cities' does not name a type
    1 |  cities numbered 1 through N, which are connected by N−1 bidirectional roads. In terms of graph theory, there is a unique simple path connecting every pair of cities. That is, the N cities form a tree. Besides, if we view city 1 as the root of this tree, the tree will be a full binary tree (a tree is a full binary tree if and only if every non-leaf vertex in the tree has exactly two children). Roads are numbered 1 through N−1. The i-th road connects city i+1 and city ai. When you pass through road i, the toll you should pay is vi (if vi is 0
      |  ^~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:201:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template