题目

给定一棵n节点的以1为根的满二叉树 (每个非叶子节点恰好有两个儿子)
n−1 条边. 第ii条边连接 i+1号点和 ai, 经过代价为vi
设这棵树有m个叶子节点
定义一次合法的旅行为:
(1) 旅行m+1天, 旅行从11号点出发, 最后回到11号点
(2) 第 1 ..m天, 每天从上一天的结束点出发, 前往一个叶子节点, 然后结束这一天
(记第0天的结束点为1)
第 m+1 天, 从上一天的结束点出发, 前往1号点
(3) 旅行过程中, 每条边恰好经过两次
定义一天的花费为 : 起点到终点的边权和
定义一次旅行的代价为: 第 2 ..m天中, 花费的**最大值**
求一种最优旅行方案, 使得旅行的代价**最小**
输出最小值

2<n<131072
1≤ai<i ∀i
0≤vi≤131072

题解

观察到$vi<=131072$，我们可以对答案ans进行二分（这种求最大值的最小，最小值的最大一般都是二分啦）

对于每一个节点$i$维护一堆$(a,b)$表示当前子树存在一条起点，终点到$i$距离分别为$a,b$且最长路径不超过$ans$的遍历完整棵子树的方案

现在讲如何合并

因为这是满二叉树，所以当前点i的方案肯定是从左儿子$lc$走到右儿子$rc$，或者反过来.

假设起点在左儿子，那么方案就是$(a,b)=(lc.a+cost_left,rc.b+cost_right)。

但是这个过程中还有$lc.end -> i -> rc.start$这条路径

所以还要满足$lc.b+cost_left+cost_right+rc.a<=ans$

但是，我们不可能对于每个$(lc.a,lc.b)$扫描所有的$(rc.a,rc.b)$

因此，对于相同的a，我们只保留最小的b，b也是同理。

另外对于$(a,b)$，如果能找到$(c,d)$使得$c<=a,d<=b$那么(a,b)就没有保留的必要

所以，我们在回溯时把每个节点的(a,b)对a从小到大排序

因为a递增，所以b递减（否则就没有保留的必要）

所以我们在合并时可以用双指针来加速合并（具体看代码）。

至于合并起点在lc内与起点在rc内的情况，可以用归并排序的思想

时间复杂度为$O(n*logn*logv)$

如果改为用数组来存每个节点的vector的话会快很多

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <map>

using namespace std;

#define N 140000

#define int long long

#define pr pair<int,int>

vector<pr> vec[N],_left,_right;

int mid;

vector<pr> dfs(int id,int from)

{

    //cout<<id<<" "<<from<<endl;

    vector<pr> lc,rc,now;

    int cl=-1,cr;

    if(vec[id].size()==1&&from)

    {

        now.push_back(make_pair(0,0));

        return now;

    }

    for(int i=0;i<vec[id].size();i++)

    {

        pr l=vec[id][i];

        if(l.first==from) continue;

        vector<pr> t=dfs(l.first,id);//返回的(a,b)的a递增，因而b递减

        if(cl<0) lc=t,cl=l.second;

        else rc=t,cr=l.second;

    }

    int j=0;

    for(int i=0;i<lc.size();i++)//选取起点在左子树，满足条件的、最优的(a,b)，新的(a,b)=(lc[i].first,rc[i].second)

    {

        while(j+1<rc.size() && lc[i].second+rc[j+1].first+cl+cr<=mid) j++;//寻找rc中满足条件的b最小的(a,b)。因为a相同时只取最小的b

        if(rc.size()&&lc[i].second+rc[j].first+cl+cr<=mid) _left.push_back(make_pair(lc[i].first+cl,rc[j].second+cr));//前面的(a,b)肯定会比当前的要差，因此不用查找rc[1~j-1]

    }

    j=0;

    for(int i=0;i<rc.size();i++)//选取起点在右子树，满足条件的、最优的(a,b)，新的(a,b)=(rc[i].first,lc[i].second)

    {

        while(j+1<lc.size() && rc[i].second+lc[j+1].first+cl+cr<=mid) j++;

        if(lc.size()&&rc[i].second+lc[j].first+cl+cr<=mid) _right.push_back(make_pair(rc[i].first+cr,lc[j].second+cl));

    }

    //此时的_left和_right一定是有序的，现在要合成一个a递增，递减的数组

    int l=0,r=0,last=0x7FFFFFFFFFFFFFFF;

    while(l<_left.size()||r<_right.size())//类似归并排序的思想

    {

        if(l<_left.size()&&(r>=_right.size()||_left[l]<=_right[r]))

        {

            if(_left[l].second<last)//为了保证now里都是最优，b要递减

            {

                last=_left[l].second;

                now.push_back(_left[l]);

            }

            l++;

        }

        else

        {

            if(_right[r].second<last)

            {

                last=_right[r].second;

                now.push_back(_right[r]);

            }

            r++;

        }

    }

    _left.clear(),_right.clear();

    return now;

}

signed main()

{

    int n;

    cin>>n;

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

    {

        int a,v;

        scanf("%lld%lld",&a,&v);

        vec[a].push_back(make_pair(i,v));

        vec[i].push_back(make_pair(a,v));

    }

    int l=0,r=17179869184;

    while(r-l>1)

    {

        mid=(l+r)/2;

        //cout<<l<<" "<<mid<<" "<<r<<endl;

        if(!dfs(1,0).empty()) r=mid;

        else l=mid;

    }

    mid=l;

    if(!dfs(1,0).empty()) cout<<l;

    else cout<<r;

}

巴特西

[AGC007E] Shik and Travel

题目

题解

代码

最新文章

热门文章