题解 P7276 【送给好友的礼物】
SSerxhs
2021-01-16 19:04:09
赛时一血，**非正解**
考虑先按照 dfs 序排序，则若一个人走过的点为序列 $\{b_n\}$，则 $b_n$ 必定是按照 dfs 序单增的。
那么有个骗分的贪心思路：可能某个人走过的 dfs 序是连续的，我们只需要枚举两个端点计算其中的答案和另一个人走过其他点的答案就可以了。计算答案的方法是计算序列中相邻两个点的距离之和，即 $dep_{b_1}+dep_{b_n}+\sum\limits_{i=1}^{n-1}dis(b_i,b_{i+1})$。这种方案的答案是两人走距离的 $\max$，最终答案是所有方案距离的 $\min$
交一发发现 wa 成 7pts
但是通过的点其实不少，那可以考虑做 $1000$ 次这个过程，每一次随机打乱子节点序列。
然后它过了
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
unsigned int x=rnd();
return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
register int c=getchar(),fh=1;
while ((c<48)||(c>57))
{
if (c=='-') {c=getchar();fh=-1;break;}
c=getchar();
}
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
x*=fh;
}
template<typename typC> void write(register typC x)
{
if (x<0) putchar('-'),x=-x;
static int st[100];
register int tp=1,y;st[1]=x%10;x/=10;
while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
const int N=1e6+2,M=1e6+2,p=998244353;
inline void inc(register int &x,const int y)
{
if ((x+=y)>=p) x-=p;
}
inline void dec(register int &x,const int y)
{
if ((x-=y)<0) x+=p;
}
inline int ksm(register int x,register int y)
{
register int r=1;
while (y)
{
if (y&1) r=(ll)r*x%p;
x=(ll)x*x%p;
y>>=1;
}
return r;
}
char s[N];
int dfn[N],top[N],d[N],siz[N],hc[N],dep[N],f[N],a[N];
vector<int> lj[N];
int T,n,m,c,i,j,k,x,y,z,ans,la;
void dfs1(int x)
{
dfn[x]=++ans;siz[x]=1;
for (int i=0;i<lj[x].size();i++) if (lj[x][i]!=f[x])
{
dep[lj[x][i]]=dep[f[lj[x][i]]=x]+1;
dfs1(lj[x][i]);
siz[x]+=siz[lj[x][i]];
if (siz[lj[x][i]]>siz[hc[x]]) hc[x]=lj[x][i];
}
}
void dfs2(int x)
{
if (hc[x])
{
int i;
top[hc[x]]=top[x];
dfs2(hc[x]);
for (i=0;i<lj[x].size();i++) if (lj[x][i]!=f[x]&&lj[x][i]!=hc[x]) dfs2(top[lj[x][i]]=lj[x][i]);
}
}
bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
inline int lca(int x,int y)
{
while (top[x]^top[y]) if (dep[top[x]]<dep[top[y]]) y=f[top[y]]; else x=f[top[x]];
return dep[x]<dep[y]?x:y;
}
inline int dis(int x,int y)
{
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
int main()
{
read(n);read(m);srand(time(0));
for (i=1;i<n;i++) read(x),read(y),lj[x].push_back(y),lj[y].push_back(x);
for (i=1;i<=m;i++) read(a[i]);ll ans=9e18;
for (int T=1;T<=100;T++)
{
memset(f+1,0,n<<2);
for (i=1;i<=n;i++) random_shuffle(lj[i].begin(),lj[i].end());
dfs1(1);dfs2(top[1]=1);
sort(a+1,a+m+1,cmp);
a[m+1]=a[1];a[0]=a[m];
for (i=1;i<=m;i++) d[i]=dis(a[i],a[i+1])+d[i-1];
for (i=1;i<=m;i++) for (j=i;j<=m;j++)
{
ll la,laa;
la=dep[a[i]]+dep[a[j]];laa=dep[a[i-1]]+dep[a[j+1]];
la+=d[j-1]-d[i-1];
laa+=d[i==1?m-1:m]-d[j]+d[i-1];
ans=min(ans,max(la,laa));
}
}
printf("%lld",ans);
}
```