AT2172 [AGC007E] Shik and Travel
题目链接：AGC007E
题面翻译
一颗n个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。
你从1号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。最后回到1号节点，要求到过所有叶子并且每条边经过恰好两次。
每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，行走路线是从叶子到叶子的那一天的路费。
求你自己最少要付多少路费？
- 2 < N < 131,072
- 1 leq a_i leq i for all i
- 0 leq v_i leq 131,072
- v_i is an integer
- The given tree is a full binary tree
Tutorial
二分答案。
设 dp[x][a][b] 表示当前在 x 点，距离第一个叶子节点的距离为 a，距离最后一个叶子节点距离为 b 是否可行。
由于是满二叉树，显然可以从其左右儿子转移过来。
直接枚举其相对顺序即可。
注意到很多都是无用状态，过滤后只存在 a 单调升，b 单调降的状态。
所以直接 two-pointers 每次转移从最小的那个转移即可。
时间复杂度大概是两个 log 的，但本人偷懒用了 sort，所以时间复杂度也说不清。。
Solution
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=131072 10;
int n;LL CUR;
#define to son[i]
#define pa pair<LL,LL>
#define mp make_pair
#define fi first
#define se second
vector<pa> v[N],g,G[N];
#define pb push_back
I void DFS(CI x,CI fa){
if(v[x].clear(),G[x].empty()) return v[x].pb(mp(0,0)),void();
LL t;RI k,i,j,ls,rs,sl,sr;for(auto i:G[x]) DFS(i.fi,x);
for(g.clear(),k=0;k<2;k ) for(ls=G[x][k].fi,rs=G[x][k^1].fi,t=CUR-G[x][0].se-G[x][1].se,sl=v[ls].size(),sr=v[rs].size(),i=0,j=0;i<sl;i ){
W(j 1<sr&&v[rs][j 1].fi<=t-v[ls][i].se) j;
j<sr&&v[rs][j].fi<=t-v[ls][i].se&&(g.pb({v[ls][i].fi G[x][k].se,v[rs][j].se G[x][k^1].se}),0);
}sort(g.begin(),g.end());for(auto i:g) (v[x].empty()||i.se<v[x].back().se)&&(v[x].pb(i),0);
}
int main(){
RI i,j,x,y,z;LL l=0,r=0,mid,X;for(read(n),i=2;i<=n;i ) read(x,z),G[x].pb({i,z}),r =z;srand(time(NULL));
W(l<=r) CUR=mid=l r>>1,DFS(1,0),!v[1].empty()?X=mid,r=mid-1:l=mid 1;
return writeln(X),0;
}
