题目链接

AtCoder：

洛谷：

Solution

首先由于每条边只能经过两次，所以每次到了\(x\)点就会遍历完\(x\)子树再出来。

考虑二分答案，设当前二分的答案为\(mid\)。

设二元组\((a,b)_x\)表示\(x\)子树下第一次走代价为\(a\)最后一次为\(b\)，且中间的过程都\(\leqslant \rm mid\)的一种方案。

那么显然可以得到一个暴力：

我们暴力枚举当前点左儿子和右儿子的二元组，设为\((a,b)_{ls},(c,d)_{rs}\)，设左儿子的边权为\(x\)，右儿子为\(y\)，那么如果满足：\(b+c+x+y\leqslant {\rm mid}\)，那么我们可以得到一个新的二元组\((a+x,d+y)_x\)。

考虑如何优化这个玩意，显然对于一个\(a\)只需要一个最小的\(b\)，对于\(b\)也同理。

所以显然可以使用\(\rm two \ pointer\)做到每次合并为\(O(sz)\)，其中\(sz\)为个数之和。

但是这样可以被卡成\(O(n^2)\)，我们加一个启发式合并，每次合并小的，那么每次最多就是\(2|\min(S_{ls},S_{rs})|\)的，总复杂度\(O(n\log^2 n\log \rm ans)\)，如果归并排序的话每次处理都是有序的，复杂度可以降为\(O(n\log n \log \rm ans)\)。

#include
    
     using namespace std;#define int long long void read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;} void print(int x) {    if(x<0) putchar('-'),x=-x;    if(!x) return ;print(x/10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf double#define ll long long#define pii pair
     
       #define fr first#define sc second#define mp make_pair#define vec vector
      
       #define pb push_back#define iter vector 
       
         :: iterator#define for_vec(i,x) for(iter i=x.begin();i!=x.end();i++) #define _sort(x,y) sort(x.begin(),x.end(),y)#define I (int)const int maxn = 3e5+10;const int inf = 1e9;const lf eps = 1e-8;int cmpx(pii x,pii y) {return x.fr
        
         rs.size()) swap(ls,rs);    //启发式合并    if(!s.empty()) s.clear();    _sort(ls,cmpy),_sort(rs,cmpx);    mn[0]=rs[0].sc;for(int i=1;i
         =0&&ls[p1].sc+rs[p2].fr>mid) p2--; if(~p2) s.pb(mp(ls[p1].fr,mn[p2])); } _sort(ls,cmpx),_sort(rs,cmpy); mn[0]=rs[0].fr;for(int i=1;i=0&&ls[p1].fr+rs[p2].sc>mid) p2--; if(~p2) s.pb(mp(mn[p2],ls[p1].sc)); }}void dfs(int x) { if(!son[x][0]) return f[x].pb(mp(0,0)),void(); int l=son[x][0],r=son[x][1];dfs(l),dfs(r); vec &ls=f[l],&rs=f[r]; for_vec(i,ls) i->fr+=v[x][0],i->sc+=v[x][0]; for_vec(i,rs) i->fr+=v[x][1],i->sc+=v[x][1]; solve(ls,rs,f[x]);ls.clear(),rs.clear();}signed main() { read(n); for(int i=2,x,y;i<=n;i++) read(x),read(y),son[x][d[x]]=i,v[x][d[x]++]=y; int 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;f[1].clear(); }write(ans); return 0;}