题解 P6584 【重拳出击】

RedLycoris · 2020-06-05 18:36:03 · 题解

做为出题人来一发（

首先，我们可以想到，敌人有很多是重复的，所以每一个位置上只留一个敌人即可。

然后，我们可以贪心的想：走到一个位置以后，等着别人来送死。

如何求出这个位置？

将这棵树，以任意一个节点为根，遍历一遍。

然后我们需要截取出“有用”的一块。（定义“有用”的一块为会被至少一个人走过的路径）

于是，我们可以让自己的初始位置为根，遍历一边这棵老树。

从所有有用的点出发，往上遍历，途中所有的点都变成有用的点。

然后删掉所有没有用的点即可。

然后，在这棵新的树上，找到最长链。

这个“最优点”一定就是这条最长链的中点了。（它到所有的叶子的距离的最大值最小。）

然后二分答案即可。

对于每一个二分到的值，循环所有有人站着的点，判断它的mid被祖先与你的初始位置的mid辈祖先之间的距离是否\le k。

这个距离也可以用LCA求出:deep[x]+deep[y]-deep[LCA(x,y)]*2

复杂度：O(n \times (log n)^2)

优化：对于最后一步，每一次二分只需要枚举3个点(自己，最长链的两端)即可。

并且将二分去掉，直接暴力即可。（删了那个预处理的nlogn）

复杂度：O(n)

贪心证明

为什么这个贪心是正确的？

你要走的话，必定向着敌人走。而且是最远的，不然没有意义。

首先，我们可以选出两个敌人(x和y)，使得他们和自己组成一个三人组，并且x到y的最短路径经过你，且你们三个人之间互相到达的最小距离最大。

然后，假设你和x的距离为a,你和y的距离为b。

如果你走向x，杀死他后再返回杀死y，那么你走到路程为max((a-k)/2,0)+max((b-k)/2,0)

待着不动的话，结果为max(max(a-k,0),max(b-k,0))

当a,b均小于k:都为0。√

当a或b小于k(一个):化简为

走向：(a-k)/2

不动： a-k

于是这个可以特判（??

不，（详细见后文）

走向：$(a-k)/2+(b-k)/2=(a+b)/2-k

不动： max(a-k,b-k)=max(a,b)-k (这里出问题了？？？

不，其实没有

因为我们要走到的标准位置上，a=b或者abs(a-b)=1

证毕。

代码：

#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
template<class T>
class myVector{
    private:
        T* data;
        int len;
        int size;
    public:
        myVector(){
            data=NULL;
            len=size=0;
        }
        void clear(){
            data=NULL;
            len=size=0;
        }
        myVector(int _len){
            data=new T[_len];
            len=_len;
            size=0;
        }
        T& operator[](int index){return data[index];}
        const myVector& push_back(const T tmp){
            if(size>=len){
                T* newData=new T[len*2+1];
                memcpy(newData,data,len*sizeof(T));
                delete []data;
                data=newData;
                len=2*len+1;
            }
            data[size++]=tmp;
            return *this;
        }
        int getSize(){return size;}
};

const uint mxn=4e5+5;
myVector<uint>g[mxn];
uint n,m,k,p[mxn],hv[mxn],son[mxn];
uint deg[mxn],par[mxn],deep[mxn];
myVector<uint>alive;
bool used[mxn];
bool ban[mxn];
void goup(register uint x){
    if(used[x] or ban[x])return;
    used[x]=1;
    for(register uint i=0;i<g[x].getSize();++i)if(deep[g[x][i]]<deep[x])goup(g[x][i]);
}
uint dfs(register uint x,uint pa,uint dep){
    if(ban[x])return 0;
    par[x]=pa,deep[x]=dep,son[x]=1;
    for(register uint i=0;i<g[x].getSize();++i)if(g[x][i]!=pa)son[x]+=dfs(g[x][i],x,dep+1);
    return son[x];
}
myVector<uint>needs;
const uint maxn=5000;
char buffer[maxn],*S,*T;
char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

uint read(){
    char c;
    uint re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

void read(register uint&x){
    char c;
    uint re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
inline int lca(int a,int b){
    if(deep[a]>deep[b])swap(a,b);
    for(;deep[b]>deep[a];)b=par[b];
    for(;a!=b;)a=par[a],b=par[b];
    return a;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    read(n);
    for(register uint i=1,u,v;i<n;++i){
        read(u),read(v);
        g[u].push_back(v);
        g[v].push_back(u);
        ++deg[u],++deg[v];
    }
    read(m);
    for(register uint i=1;i<=m;++i)read(p[i]),hv[p[i]]=1;
    read(k),read(p[m+1]);hv[p[m+1]]=1;
    dfs(1,1,1);
    myVector<uint>vhv;vhv.clear();
    for(register uint i=1;i<=n;++i)if(hv[i])vhv.push_back(i);
    uint Root=vhv[0];
    dfs(Root,Root,1);
    for(register uint i=0;i<vhv.getSize();++i)goup(vhv[i]);
    for(register uint i=1;i<=n;++i)if(!used[i])ban[i]=1;
    alive.clear();
    for(register uint i=1;i<=n;++i)if(!ban[i])alive.push_back(i);
    if(!alive.getSize()){
        cout<<1<<endl;
        return 0;
    }
    memset(par,0,sizeof(par));
    dfs(alive[0],alive[0],1);
    uint mx=0,wz=0;
    uint po1,po2;
    for(register uint i=1;i<=n;++i)if(!ban[i] and deep[i]>mx){
        mx=deep[i];
        wz=i;
    }
    po1=wz;     
    dfs(wz,wz,1);
    mx=0,wz=0;
    for(register uint i=1;i<=n;++i)if(!ban[i] and deep[i]>mx){
        mx=deep[i];
        wz=i;
    }
    po2=wz;
    uint mypos=p[m+1];
    uint ln=deep[po2]-1;
    uint md=po2;
    for(register uint i=1;i<=ln/2;++i)md=par[md];
    dfs(md,md,1);Root=md;
    needs.push_back(po1);needs.push_back(po2);needs.push_back(p[m+1]);
    uint a=po1,b=po2,c=p[m+1];
    bool da=0,db=0;
    int lac=lca(a,c),lbc=lca(b,c);
    bool ha=0,hb=0;
    for(register uint ans=1;ans<=ln;++ans){
        if(!da and deep[c]+deep[a]-2*deep[lac]<=k)da=1;
        if(!db and deep[c]+deep[b]-2*deep[lbc]<=k)db=1;
        if(da and db){
            cout<<ans<<'\n';
            return 0;
        }
        if(a==lac or c==lac)ha=1;
        if(b==lbc or c==lbc)hb=1;
        if(a!=md)a=par[a];
        if(b!=md)b=par[b];
        if(c!=md)c=par[c];
        if(ha)lac=par[lac];
        if(hb)lbc=par[lbc];

    }
    return 0;
}

题解 P6584 【重拳出击】

贪心 证明

贪心证明