AT2172 [AGC007E] Shik and Travel

(Updated: )
oi
,

题目链接：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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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%10+'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;
}