【点分治】洛谷P5306 Transport 题解

说的石门模拟测试，这题叫作“加油”。

一开始以为树形dp呢，想后认为是点分治。

题目

[COCI2018-2019#5] Transport - 洛谷

一个国家有n个城市，每个城市中都有一个加油站，燃料储量为ai。  
有n-1条路径，将这些城市连接成一个树形结构。  

一个货车能从城市u到达城市v，货车的燃料量必须不小于u,v之间的距离。  
每当货车抵达一个城市，就可以补充不超过加油站储量的燃料。  

假设货车的油箱是无限大的，请你算出有多少个有序数对(u,v)满足：  
一个油箱燃料量初始为0的货车，可以从城市u出发，抵达城市v。

请注意，货车只能走简单路径，也就是说不能走回头路。

思路

如前面所说，这题是个点分治

设有一段过重心root的路径a→b，那么它可以分成：a→root→b，考虑分段处理：

a→root（上行路径）：

以root为根，求它到树上各点u的总油量（点权）和总路程

对于一个路径a→root，其上有一点u；当a→root合法，则：

等价于：

发现在dfs即get_dis函数里面，这是不好统计的，于是考虑不等式变形：

转化成了每个点的you值与d值之差（单独信息）！

则在get_dis当中取一个ma，即的最大值，可以判断一个点a能否成为上行路径“a→root”的起点；若可以，则将符合条件a点的you值与d值之差压入栈s1，作为可选择的起点，至于为什么存差值，实则是在考虑root→b时有用处。

root→b（下行路径）：

对于一个路径root→b，其上有一点v；当root→b合法，记y为其中一个可行的a的上行路径“a→root”的剩余油量，就是刚刚栈s1存的东西（揭示s1中存差值的作用：方便在考虑root→b时获取剩余油量y），则：

等价于

其中fa[v]表示v的父亲

发现a→root→b类似于a←root←b，那么在考虑a→root时，对a←root←b的下行路径root→a进行处理；但是会发现上文的不等式只能在后面判断，所以用一个栈s2记：在root→a上的v的you值与d值之差的最小值（get_dis中调用mi参数）

是不是都转晕了，来看看get_dis函数的代码实现吧：

void get_dis(ll u,ll fa,ll ma,ll mi)
{
	if(you[u]-d[u]>=ma)s1[++cnt1]=ma=you[u]-d[u];//上文中的a→root的a，可行就压入s1
	s2[++cnt2]=mi;
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to,w=e[i].w,tem;
		if(v==fa||vis[v])continue;
		you[v]=you[u]+a[v];//在这里的dfs(get_dis)中，u是v的父亲，即上文中的fa[v]
		d[v]=d[u]+w;
        //分别预处理you数组和d数组
		tem=min(mi,you[u]-d[v]);
		get_dis(v,u,ma,tem);
	}
}

合并答案

对于一个路径j→k，当时（很好理解，就是j→k的点权和应大于边权和，注意要减去重复算了的root的点权a[root]），且根据上文定义j→k应当经过root（即分居root两侧的不同子树）应当那么这条路径就是合法的。

发现不同子树的不好统计；但是如果考虑统计所有合法的，并减去子树里所有合法的（转化为子问题），就比较好统计，即容斥原理，用式子概括为：

不同子树 j→k = 所有 j→k - 同一子树 j→k 

可以先处理同一子树的j→k，在总答案上先减去，并将每个子树的两栈s1和s2总合进整体栈t1和t2，最后再集中处理t1和t2对答案的贡献。

怎么处理两个栈的贡献呢？举处理栈s1和栈s2的负贡献为例：因为要求满足，所以考虑对两个栈排序，选其中一个栈作为“主元”，借助双指针来统计贡献，先奉上代码：

sort(s1+1,s1+cnt1+1);//cnt1:s1栈长
sort(s2+1,s2+cnt2+1);//cnt2:s2栈长
ll k=1;//双指针
for(int j=cnt2;j>=1;j--)
{
	while(k<=cnt1&&s1[k]+s2[j]<you[u])k++;//统计最小满足上文中的不等式的指针k
	ans-=cnt1-k+1;//因为两栈已经排了序，所以[k,cnt1]的s1值有贡献，减去个数（会算吧）
}

t1和t2的处理方法大差不差，不过要注意：root→b自己也可能产生贡献，即：当k=root、j=b时，有，那么当时，也是合法的，贡献加一；同样的所有存在整体栈t1的a→root也都能产生贡献，最后的贡献记得加上t1的栈长！

奉上处理t1和t2的代码：

sort(t1+1,t1+tnt1+1);//tnt1:t1栈长
sort(t2+1,t2+tnt2+1);//tnt2:t2栈长
ll k=1;//双指针
for(int j=tnt2;j>=1;j--)
{
	if(t2[j]>=0)ans++;
	while(k<=tnt1&&t1[k]+t2[j]<you[u])k++;
	ans+=tnt1-k+1;
}
ans+=tnt1;

其它的就是点分治的知识了。这种解法的时间复杂度也达到了点分治的优秀复杂度，对于n=1e5完全吃得消！

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+9,inf=0x7f7f7f7f;
ll n,a[N],u,v,w,ans;
ll idx,head[N];
struct edge
{
	ll to,next,w;
}e[N<<1];
void addedge(ll u,ll v,ll w)
{
	idx++;
	e[idx].to=v;
	e[idx].next=head[u];
	e[idx].w=w;
	head[u]=idx;
}
ll root,siz[N],mx[N],S;
ll cnt1,cnt2,s1[N],s2[N];
ll tnt1,tnt2,t1[N],t2[N];
ll you[N],d[N];
bool vis[N];
void findroot(ll u,ll fa)
{
	siz[u]=1;
	mx[u]=0;
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to;
		if(v==fa||vis[v])continue;
		findroot(v,u);
		siz[u]+=siz[v];
		mx[u]=max(mx[u],siz[v]);
	}
	mx[u]=max(mx[u],S-siz[u]);
	if(mx[u]<mx[root])root=u;
}
void get_dis(ll u,ll fa,ll ma,ll mi)
{
	if(you[u]-d[u]>=ma)s1[++cnt1]=ma=you[u]-d[u];
	s2[++cnt2]=mi;
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to,w=e[i].w,tem;
		if(v==fa||vis[v])continue;
		you[v]=you[u]+a[v];
		d[v]=d[u]+w;
		tem=min(mi,you[u]-d[v]);
		get_dis(v,u,ma,tem);
	}
}
void cal(ll u)
{
	you[u]=a[u];
	d[u]=0;
	tnt1=tnt2=0;
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to,w=e[i].w;
		if(vis[v])continue;
		you[v]=you[u]+a[v];
		d[v]=d[u]+w;
		cnt1=cnt2=0;
		get_dis(v,u,you[u]-d[u],you[u]-d[v]);
		sort(s1+1,s1+cnt1+1);
		sort(s2+1,s2+cnt2+1);
		ll k=1;//双指针
		for(int j=cnt2;j>=1;j--)
		{
			while(k<=cnt1&&s1[k]+s2[j]<you[u])k++;
			ans-=cnt1-k+1;
		}
		for(int j=1;j<=cnt1;j++)
		t1[++tnt1]=s1[j];
		for(int j=1;j<=cnt2;j++)
		t2[++tnt2]=s2[j];
	}
	sort(t1+1,t1+tnt1+1);
	sort(t2+1,t2+tnt2+1);
	ll k=1;//双指针
	for(int j=tnt2;j>=1;j--)
	{
		if(t2[j]>=0)ans++;
		while(k<=tnt1&&t1[k]+t2[j]<you[u])k++;
		ans+=tnt1-k+1;
	}
	ans+=tnt1;
}
void sol(ll u)
{
	vis[u]=1;
	cal(u);
	for(int i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to,w=e[i].w;
		if(vis[v])continue;
		S=siz[v];
		root=0;
		mx[0]=inf;
		findroot(v,u);
		sol(root);
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	S=n;
	root=0;
	mx[0]=inf;
	findroot(1,0);
	sol(root);
	printf("%lld",ans);
	return 0;
}