HDU5956 The Elder 下凸壳的维护

题意：

一棵树，1为根。每个点只能走向祖先，时间为距离的平方，另外走到祖先后会停留P单位时间。求每个点到达根的最小时间的最大值。

思路：

显然dp方程为:f[i]=(d[i]-d[j])^2+P+f[j]  ( j 是 i 的祖先）

转化成向量点积形式：f[i]=d[i]^2+P+(1 , 2*d[i] ) * ( f[j]+d[j]^2 , -d[j] )

注意到深度越大，向量(1 , 2*d[i] )会逆时针旋转

于是维护点集i的所有祖先的  ( f[j]+d[j]^2 , -d[j] ) 的下凸壳，就能求出f[i]的最小值

注意到向量( f[j]+d[j]^2 , -d[j] )只会添加在下凸壳右边，于是只要用个队列来保存就可以了

查询的时候只要一直扔掉左边的点，找到最大值为止，然后退出当前dfs的时候加回来就可以了

如果一个个保存删掉的点，再一个个加回来的话，在菊花图的情况下复杂度就会变成O（n^2），事实上目前网上的题解都是这么做的，估计出题人也没意识到复杂度的问题，因为这看起来很像O（n）。

我的做法是每次dfs记录当前队列的左端点，和右端点，操作完后，事实上只是替换了数组里的tail位置的元素，把head和tail还有这个元素事先保存下来，最后恢复head，tail和这个元素就可以了，这样复杂度就是完美的O（n）了。

也不知道这种做法叫什么，毕竟自己乱想出来的，就叫回溯队列好了233

后来一想这个做法还是n方。。。因为每次head和tail的删除操作都可能是O（n）的，所以要二分查找head和tail分别应该删到哪，这样算法复杂度就是O（nlogn）了

这里如果不用斜率，而把两边的dx都乘到对面去的话是有问题的，因为f[j]+d[j]^2的规模是1e14，2*d[i]的规模是1e7，乘起来理论上会爆，然而数据好像还是没卡掉这种做法

代码1：O（n^2）做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
	ll x,y;
	ll operator*(const P &b)const
	{
		return x*b.x+y*b.y;
	}
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
	long double tmp=1.0;
	return tmp*(b.y-a.y)/(b.x-a.x);
}
void dfs(int u,int fa,int deep)
{
	int phead=head,ptail=tail;
	d[u]=deep;
	if (u==1) f[u]=-p;
	else
	{
		P tmp={1,2*d[u]};
		while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
		f[u]=d[u]*d[u]+p+stk[head]*tmp;
	}
	P tmp={f[u]+d[u]*d[u],-d[u]};
	while(tail-head+1>=2&&
		slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
	P mem=stk[tail+1];
	stk[++tail]=tmp;

	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i].x;
		if (v==fa) continue;
		dfs(v,u,deep+link[u][i].y);
	}
	tail--;
	stk[tail+1]=mem;
	head=phead; tail=ptail;
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&p);
		for (int i=1;i<n;i++)
		{
			ll x,y,z;
			scanf("%d%d%lld",&x,&y,&z);
			if (z<0) n/=0;
			link[x].push_back({y,z});
		}
		head=1; tail=0;
		dfs(1,1,0);
		ll ans=0;
		for (int i=1;i<=n;i++) ans=max(ans,f[i]);
		printf("%lld\n",ans);

		for (int i=1;i<=n;i++) link[i].clear();
	}
}

代码2：O（nlogn）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
    ll x,y;
    ll operator*(const P &b)const
    {
        return x*b.x+y*b.y;
    }
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
    long double tmp=1.0;
    return tmp*(b.y-a.y)/(b.x-a.x);
}
int gethead(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (stk[mid]*v>=stk[mid+1]*v) l=mid+1;
		else r=mid;
	}
	return l;
}
int gettail(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (slope(stk[mid],stk[mid+1])<slope(stk[mid+1],v)) l=mid+1;
		else r=mid;
	}
	return l;
}
void dfs(int u,int fa,int deep)
{
    int phead=head,ptail=tail;
    d[u]=deep;
    if (u==1) f[u]=-p;
    else
    {
        P tmp={1,2*d[u]};
        head=gethead(tmp);

        //while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
        f[u]=d[u]*d[u]+p+stk[head]*tmp;
    }
    P tmp={f[u]+d[u]*d[u],-d[u]};
    tail=gettail(tmp);
//    while(tail-head+1>=2&&
//        slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
    P mem=stk[tail+1];
    stk[++tail]=tmp;

    for (int i=0;i<link[u].size();i++)
    {
        int v=link[u][i].x;
        if (v==fa) continue;
        dfs(v,u,deep+link[u][i].y);
    }
    tail--;
    stk[tail+1]=mem;
    head=phead; tail=ptail;
}
int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&p);
        for (int i=1;i<n;i++)
        {
            ll x,y,z;
            scanf("%d%d%lld",&x,&y,&z);
            link[x].push_back({y,z});
        }
        head=1; tail=0;
        dfs(1,1,0);
        ll ans=0;
        for (int i=1;i<=n;i++) ans=max(ans,f[i]);
        printf("%lld\n",ans);

        for (int i=1;i<=n;i++) link[i].clear();
    }
}