洛谷 P6419 Kamp 题解

明天就SX AFO了交篇题解%一下

这题大概是我第一道有独立思考切掉的紫题

之前的都是各种抄借鉴题解

为什么写这题的题解呢?另一个重要的原因是这样的↓

翻了翻已有题解中的几篇，下面几种情况屡见不鲜

样例2都过不去论题解是如何过审的
变量名不统一，有一些小的笔误
疯狂的防作弊系统，复制编译试图对拍然鹅数十行报错

正因如此，本蒟蒻想道自己写一篇题解，尽量保证不出现上面的错误，如果依然有笔误请轻喷

因为作者忙着复习颓废，$Markdown$及$Latex$会有一点偷懒，敬请谅解

说了一堆废话，下面进入正题

树形dp+换根

两遍dfs

这俩思想应该还是比较容易想到，像这种暴力搞不了的树上问题一看就是dp，再一个题目要求每一个点的情况，暴力跑一定会爆炸，所以需要用到换根

观察题目性质

问题可以简化成，在某一节点$i$聚会时，此时的答案即为司机把所有人送回家再返回该点的距离减掉从点$i$到最远的人的家的距离。
如果我们走的是简单路径（不知道简单路径是什么的可以当场AFO了），那么是不存在所谓的最短路的，因为这是一棵树，先送道远的和先送道近的没有本质区别

下面我们来设计状态

首先我们以$1$号节点为根

$g[u]$ 从点u出发把所有在u的子树里的人送回家并返回u的距离

$f[u]$ 从点$u$出发把所有人出发并返回$u$的距离

$len[u]$ 从$u$出发，在$u$的子树内，距离$u$最远的那个人的家到$u$的距离

$dlen[u]$ 从$u$出发，在$u$的子树内，距离$u$次远第二远的那个人的家到$u$的距离

$up[u]$ 不在u的子树内，距离$u$最远的那个人的家到$u$的距离

$siz[u]$ $u$及$u$的子树内有多少个人的家

则最终的答案应为

$ans[i] = f[i] - max(up[i],len[i] ) $

那么我们考虑代码

第一次$dfs$我们主要是处理子树内的问题

我们需要处理出$ g[]$,$len[]$,$dlen[]$，$siz[] $

这应该很简单

第二次就是换根操作了

我们需要处理出$up[],f[]$

我们需要分类讨论，设当前的点为$u$，父亲节点为$fa$，这条边的边权为 _$w$

当所有人的家都在$u$的子树内即$siz[u]=k$时，这时候$f[u]$即是$g[u]$，而$up[u]$应当是$0$，这很显然，因为$u$的子树外没有家
当所有人的家都不在u的子树内即$siz[u]=0$时，这是$f[u]=f[fa]+2$_$w$,因为你首先要走到父亲节点这样才能送人回家，$up[u]$则完全由父亲节点更新（详见代码）
$u$的子树内有家，$u$的子树外也有家时，这种情况可以手玩一下，$f[u]$就等于$f[fa]$ ，那么$ up[u]$呢？我们感性理解一下，$up[u]$时$u$从他的父亲那里继承而来的最长链，而$len[u]$,$dlen[u]$则是从儿子那里继承过来的最长次长链那么我们显然要分两种情况

当$u$在他父亲的$len[fa]$上时，$up[u]$就需要从$dlen[fa]$更新过来因为$len[fa]$要经过$u$
当$u$不在父亲的$len[fa]$上时，同理由$len[fa]$转移过来

讲的比较抽象，建议画图+阅读代码理解

十年OI一场空，不开long long见祖宗

Code:

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn = 5e+5+100;

struct Edge{

	int v;

	ll w;

};

int n,k;

int he[maxn],ne[maxn<<1],cnt=1;

Edge G[maxn<<1];

bool p[maxn];

int siz[maxn];

ll f[maxn],g[maxn],up[maxn],len[maxn],dlen[maxn];

void add_Edge(int u,int v,ll w){

	G[cnt].v = v;

	G[cnt].w = w;

	ne[cnt] = he[u];

	he[u] = cnt++;

}

void dfs(int u,int fa){

	siz[u] = p[u];

	for(int i=he[u];i;i=ne[i]){

		int v=G[i].v;

		int w=G[i].w;

		if(v==fa) continue;

		dfs(v,u);

		siz[u]+=siz[v];

		if(siz[v]){

			g[u] += g[v] + 2*w;

			if(len[v]+w>len[u]){

				dlen[u] = len[u];

				len[u] = len[v] + w;

			}

			else if(len[v]+w>dlen[u]){

				dlen[u] = len[v] + w;

			}

		}

	}

}

void dfs(int u,int fa,ll _w){

	if(siz[u]==k){

		f[u] = g[u];

		up[u] = 0;

	}

	else if(siz[u]==0){

		f[u] = f[fa] + 2*_w;

		up[u] = max(up[fa],len[fa]) + _w;

	}

	else{

		f[u] = f[fa];

		if(len[fa]-len[u]==_w) up[u] = max(up[fa],dlen[fa]) + _w;

		else up[u] = max(up[fa],len[fa]) + _w;

	}

	for(register int i=he[u];i;i=ne[i]){

		int v=G[i].v;

		int w=G[i].w;

		if(v==fa) continue;

		dfs(v,u,w);

	}

}

int main(){

	cin>>n>>k;

	for(register int i=1;i<n;++i){

		int u,v;

		ll w;

		scanf("%d%d%lld",&u,&v,&w);

		add_Edge(u,v,w);

		add_Edge(v,u,w);

	}

	for(register int i=1;i<=k;++i){

		int x;

		scanf("%d",&x);

		p[x] = true;

	}

	dfs(1,0);

	dfs(1,0,0);

	for(register int i=1;i<=n;++i) printf("%lld\n",f[i]-max(up[i],len[i]));

	return 0;

}

巴特西

洛谷 P6419 Kamp 题解

树形dp+换根

两遍dfs

观察题目性质

最新文章

热门文章