【AGC007E】Shik and Travel

【AGC007E】Shik and Travel

by AmanoKumiko

Description

给一颗\(N\)个点的树，每个点要么有两个儿子要么是叶子

任意选定一个叶子作为起点，然后要进行\(M-1\)天（\(M\)为叶子个数）的旅行

每次去到一个没经过的叶子，同时在整个过程中每条边的经过次数不超过\(2\)

求最小的最大的每天的旅行的距离

Input

第一行一个数\(N\)

然后\(N-1\)行，第\(i\)行读入\(fa_{i+1},a_{i+1}\)

Output

一行一个整数表示答案

Sample Input

9
1 26166
1 278
2 23731
2 17834
5 4105
5 19470
6 28803
6 3445

Sample Output

52378

Data Constraint

\(2\le N\le 10^5\)，\(0\le a_i\le 10^5\)

Solution

先二分答案

容易发现一定会遍历完某一个子树再遍历它的另一个子树

那我们设一个二元组\((u,v)\)表示在某个子树中，存在起点为\(u\)，最后到达\(v\)，

且中间的所有距离不大于\(mid\)的路径

那么直接做就能得到\(O(n^2)\)的好成绩

我们考虑优化

令合并的起点为\((u1,v1)\)，终点为\((u2,v2)\)

把柿子写出来\(dis_{v1}+dis_{u2}-2dis_{root}\le mid\)

那么作为起点时，钦定\(u1\)则需要最小化\(dis_{v1}\)

作为终点同理

这样删除掉不优的状态后就能得到\(O(nlog^2n)\)的复杂度

合并可以用双指针（但我懒所以不想写

Code

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define inf 10000000000000
#define LL long long
#define N 100010

LL le,ri,dis[N],mid;
int n,a[N],ls[N],rs[N];
struct point{int u,v;};

bool cmp1(const point&le,const point&ri){
	return dis[le.u]s1[N],s2[N];

void dfs(int x){
	if(ls[x]){
		dis[ls[x]]=dis[x]+a[ls[x]];dfs(ls[x]);
		dis[rs[x]]=dis[x]+a[rs[x]];dfs(rs[x]);
	}
}

int tp;

void calc(int x){
	tp++;
	if(ls[x]){
		calc(ls[x]);calc(rs[x]);
		if(s2[ls[x]].size()&&s1[rs[x]].size()){
			int lstpos=0;
			F(i,0,s2[ls[x]].size()-1){
				LL Min=inf;int pos=0;
				F(j,0,s1[rs[x]].size()-1){
					if(dis[s1[rs[x]][j].u]<=dis[x]*2+mid-dis[s2[ls[x]][i].v]){
						if(dis[s1[rs[x]][j].v]>1,check()?ri=mid:le=mid;
	printf("%d",ri);
	return 0;
}