P6584 重拳出击 题解

发表于 分类于

本文迁移自洛谷原文。

做为出题人来一发（

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

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

如何求出这个位置？

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

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

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

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

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

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

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

然后二分答案即可。

对于每一个二分到的值，循环所有有人站着的点，判断它的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,b$均大于$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$

证毕。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#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;
}