P6419 [COCI2014-2015#1] Kamp
ADNAP
·
·
题解
这是一个 6 个 dfs 加上 LCA 的做法。写完看了一遍题解都是换根 dp 和树剖。
手模一下，第 i 个点的答案可以这样计算，设由这个点和 k 个被选点组成的极小的子树的边权和为 Sum，设点 i 到 k 个点的最长距离为 mx，则：
理解一下就是假若送完 $k$ 个人后要回到起点，那么一进一出，每条边的贡献就要算 $2$ 次。
解除了回到原点的限制，即说明到了最后一个点之后到起点的路径不算贡献，我们当然希望这条边越长越好，因此是最长路径。
考虑实现：
- 我们用第一个 dfs 来处理 LCA 需要用到的信息。
- 第二个 dfs 标记由 $k$ 个点形成的 **虚树** 中的点以及边，同时计算虚树上的边权和，记为 $Sum'$。
- 第三个 dfs 跑一下虚树外的点到虚树的距离。记为 $dise_i$。
- 第五个和第六个 dfs 用来计算虚树上的点到被选的 $k$ 个点的最长距离，记为 $disv_i$。具体计算方式是，我们跑第五个dfs时，同时维护由父节点过来的最长距离，到节点 $u$ 时，用第五个 dfs 找向下的最长距离和次长距离。据此求出子节点递归时的维护信息，再往下递归第五个 dfs 即可。
- 第四个 dfs 在上面两个 dfs 的基础上计算虚树外的点到被选的 $k$ 个点的最长距离 $disv_i$。
最后统计答案：
\begin{aligned}
ans&=2 \times Sum-mx\
&=2 \times (Sum'+dise_i)-disv_i
\end{aligned}
时间复杂度是 $O(n \log n)$，瓶颈在 LCA，精细实现可以达到 $O(n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+1e2,M=N<<1;
ll n,k;
ll a[N];
ll h[N],t[M],weigh[M],nex[M],cnt;
void add(ll u,ll v,ll w)
{
++cnt;
t[cnt]=v;
weigh[cnt]=w;
nex[cnt]=h[u];
h[u]=cnt;
}
ll Lca,faLca;
ll fa[N][20],dep[N],dist[N];
void dfs(ll u,ll f)
{
if(u==Lca)faLca=f;
fa[u][0]=f,dep[u]=dep[f]+1;
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f)continue;
dist[j]=dist[u]+weigh[i];
dfs(j,u);
}
}
ll lg2[N];
void init()
{
for(ll i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
for(ll i=1;i<=lg2[n];i++)
for(ll j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
}
ll lca(ll x,ll y)
{
if(dep[x]<dep[y])swap(x,y);
ll d=dep[x]-dep[y];
while(d)
{
ll k=lg2[d];
x=fa[x][k];
d-=(1<<k);
}
if(x==y)return x;
ll mx_up=lg2[dep[x]];
for(ll i=mx_up;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
bool used[N];
bool used_e[M];
ll sum;
bool dfs2(ll u,ll f)
{
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f)continue;
if(dfs2(j,u))
{
used[u]=true;
used_e[i]=true;
sum+=weigh[i];
}
}
if(used[u])return true;
return false;
}
ll dis_e[N],dis_v[N];
void dfs3(ll u,ll f)
{
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f||used[j])continue;
dis_e[j]=dis_e[u]+weigh[i];
dfs3(j,u);
}
}
void dfs4(ll u,ll f)
{
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f||used[j])continue;
dis_v[j]=dis_v[u]+weigh[i];
dfs4(j,u);
}
}
ll dfs6(ll u,ll f)
{
ll res=0;
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f||!used[j])continue;
res=max(res,dfs6(j,u)+weigh[i]);
}
return res;
}
void dfs5(ll u,ll f,ll mx)
{
ll fir=0,sec=0;
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f||!used[j])continue;
ll res=dfs6(j,u)+weigh[i];
if(res>fir)sec=fir,fir=res;
else if(res>sec)sec=res;
}
dis_v[u]=max(mx,fir);
for(ll i=h[u];i;i=nex[i])
{
ll j=t[i];
if(j==f||!used[j])continue;
ll tot=dfs6(j,u)+weigh[i];
if(tot==fir)
dfs5(j,u,max(mx+weigh[i],sec+weigh[i]));
else dfs5(j,u,max(mx+weigh[i],fir+weigh[i]));
}
}
signed main()
{
memset(dis_e,127,sizeof dis_e);
scanf("%lld%lld",&n,&k);
for(ll i=1;i<n;i++)
{
ll x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
for(ll i=1;i<=k;i++)
scanf("%lld",&a[i]),used[a[i]]=true,dis_v[a[i]]=0;
dfs(1,0);
init();
Lca=a[1];
for(ll i=2;i<=k;i++)
Lca=lca(Lca,a[i]);
dfs(1,0);
dfs2(Lca,faLca);
sum<<=1;
for(ll i=1;i<=n;i++)
if(used[i])
{
dis_e[i]=0;
dfs3(i,0);
}
dfs5(a[1],0,0);
for(ll i=1;i<=n;i++)
if(used[i])
dfs4(i,0);
for(ll i=1;i<=n;i++)
{
ll res=0;
res=sum+(dis_e[i]<<1)-dis_v[i];
printf("%lld\n",res);
}
}
```