AtCoder Grand Contest 007 E：Shik and Travel

题目传送门：https://agc007.contest.atcoder.jp/tasks/agc007_e

题目翻译

现在有一个二叉树，除了叶子每个结点都有两个儿子。这个二叉树一共有\(m\)个叶子，你需要从\(1\)号点出发，旅行\(m+1\)天后回到\(1\)号结点，其中前\(m\)天每天需要在叶子节点结束，并且每个叶子结点只允许被经过一次，每条边只允许被经过两次，边有边权，旅行的费用即为两点之间简单路径上权值之和，然后问你费用最大的一天最小可以是多少。第一天和最后一天免费。

题解

嗯，这又是一道题解题……

我们考虑二分答案，那么问题就转化成了怎么判断“每天花费都不超过\(limit\)是否可以完成旅途”。由于每条边只允许被经过两次，所以每个子树只允许被进出一次各一次。我们设\(f_{ijk}\)表示\(i\)号点子树第一次进去花费\(j\)，出来花费\(k\)，内部叶子节点走来走去不超过\(limit\)是否可以做到。因为边权过大，状态存不下来，所以我们用\(vector\)存三元组\(<i,j,k>\)来表示这个状态为真。当\(j\)相同时我们只存较小的\(k\)，所以状态个数只会有\(NlogN\)个。然后每次由两个儿子转移更新自己可以用归并排序，按\(j\)从小打大排。

时间复杂度：\(O(NlogNlogANS)\)

空间复杂度：\(O(NlogN)\)

代码如下：

#include <vector>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

typedef vector<pll> vp;

#define fr first

#define sc second

const int maxn=131073;

int n,tot;

ll dis[maxn];

int son[maxn][2],num[maxn];

ll l,r=1ll*maxn*maxn,limit;

vp f[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

vp dp(vp a,vp b) {

	vp res;res.clear();

	int x=a.size(),y=b.size(),st1=0,st2=0;

	if(!y)return res;

	while(st1!=x) {

		while(st2!=y&&a[st1].sc+b[st2].fr<=limit)st2++;

		if(st2)st2--;

		if(a[st1].sc+b[st2].fr<=limit)res.push_back(make_pair(a[st1].fr,b[st2].sc));

		st1++;

	}

	return res;

}

void insert(vp &a,pll b) {

	if(a.empty())a.push_back(b);

	else if(a.back().fr==b.fr)a.back().sc=min(a.back().sc,b.sc);

	else if(b.sc<a.back().sc)a.push_back(b);

}

vp merge(vp a,vp b) {

	vp res;res.clear();

	int x=a.size(),y=b.size(),st1=0,st2=0;

	while(st1!=x&&st2!=y) {

		if(a[st1].fr<b[st2].fr)insert(res,a[st1++]);

		else insert(res,b[st2++]);

	}

	while(st1!=x)insert(res,a[st1++]);

	while(st2!=y)insert(res,b[st2++]);

	return res;

}

void dfs(int u) {

	if(!num[u]) {

		f[u].clear();

		f[u].push_back(make_pair(dis[u],dis[u]));

		return;

	}

	dfs(son[u][0]),dfs(son[u][1]);limit+=dis[u]*2;

	vp tmp1=dp(f[son[u][0]],f[son[u][1]]);

	vp tmp2=dp(f[son[u][1]],f[son[u][0]]);

	f[u]=merge(tmp1,tmp2);

	limit-=dis[u]*2;

}

bool check() {

	dfs(1);

	if(!f[1].empty())return 1;

	return 0;

}

int main() {

	n=read();

	for(int i=2;i<=n;i++) {

		int fa=read(),v=read();

		dis[i]=dis[fa]+v;

		son[fa][num[fa]++]=i;

	}

	while(l<r) {

		limit=(l+r)>>1;

		if(check())r=limit;

		else l=limit+1;

	}

	printf("%lld\n",r);

	return 0;

}