题解 P3629 【[APIO2010]巡逻】
Wow_Goodjob · · 题解
From 多年不写题解的蒟蒻
先吐槽一句某谷的评测机,我有一份提交一直N/A
正解为 ：树的直径+数学推断
-------------------------------下面是真_题解--------------------
RT,有一棵树，要求我们在树上加上1~2两条边，是警察遍历时经过的路径最短，关于路径，有以下几个要求
- 造出来的路必须且仅经过一遍
- 允许出现某条路有某点连向同一个点
- 从1好节点出发，回到一号节点
好了让我们开始思考，只要我们认真地读题了，就会发现k只有两种情况:k==1或k==2，那么不妨进行一波分类讨论
k==1时
当k==1时，发现，只要不zz一般地从自己连到自己(造的路必须通过)，都是可以帮警察省下路程的，所以我们不妨考虑一下贪心地选择，即选择树上距离最长的两点，因为不管我们选择了那两个点，省下的距离都是两点之间的距离 - 1（走造的那条路还要 1） 那么我们只要找到距离最大的两个点就可以省下最长的路程这就引出了我们的主角——树的直径
树的直径
什么是树的直径呢？其实就是树上距离相差最大的两个点之间的路径，概念非常好理解，代码也不长
怎么树的直径
- 两次dfs
- 树形dp
两种方法各有优缺点将在先问中讲到
dfs求树的直径
其实就是在树上随机选一个点，对他进行一次dfs求出距离它距离最远的一个点A,然后再用那一个点dfs回来找到一个离A点距离最远的B点，AB之间的路径即为树的直径
代码:(dfs)
void dfs(int x,int father,int weight){
if(weight>=_max){
_max=weight;
id=x;
}
for(int i=linkk[x];i;i=e[i].nxt)
if(e[i].to!=father)
dfs(e[i].to,x,weight+e[i].value);
}优点:可以记录直径的起点，重点，再配合一个dfs可以求出直径上的每一个点
缺点:遇到副边权的树就GG
树上dp求树的直径
通过树形dp的方式，通过求出差不多每个点之间的距离，求最大值，听上去比较难理解，但学过树形dp的同学应该都知道码量比较小
代码:(树上dp)
void Dp_to_Find_D_afther(int now,int father){
for(int i=linkk[now];i;i=e[i].nxt){
if(e[i].to==father) continue;
Dp_to_Find_D_afther(e[i].to,now);
Dafter=max(Dafter,dis[now]+dis[e[i].to]+e[i].value);
dis[now]=max(dis[now],dis[e[i].to]+e[i].value);
}
}优点:可以处理负边权的树
缺点:真的只能求一个树的直径的长度，其他的求不出
两种方法互相补充，正是这题的优秀之处，它同时考到了两种算法
然后当k==1时，就可以省下树的直径-1的路啦(显然这是省的最多的)，由于本来要走的路程是(N-1)<<1(每条路走两次),我们当k==1时的答案就是
(2*(N-1)-Dfront+1)//Dfront是树的直径k==2时
这是这道题目的难点所在，但如果想通了k==1时的情况的话，其实也不是很难然而本蒟蒻还是卡了差不多一个上午我们在求出了一开始求出了树的直径之后，我们可以把造的那条边先忽略掉，然而，要怎么解决有些边已经被省下的情况呢？
首先，我们得发现，当我们加入了一条边后，就多了一个环这棵树就变成了一颗基环树，所以当我们加入第二条边时，他会出现第二个环，这个环的情况也不多，不如再来一波分类讨论
- 此环的边和第一个环有重叠
- 此环的边和第一个环没有重叠
当第二种情况时，不用想就应该知道，只要再贪心一次(把第一条直径上的边忽略)就可以了，所以我们真正的挑战在第一种情况
敲黑板，以下是重点
当我们的第二个环有与第一个环有重边时，因为造出来的路必须只经过一次，所以这个环肯定是要遍历一次的，也就是相当于我们第一次造路并没有帮重叠的边省下路程，那么怎么处理这种情况呢？？
想必各位dalao都知道，
x-y-(-y)=xbingo!!!我们只要把第一条直径上的边的边权改为 -1 (或一个你喜欢的负数) 就行啦
敲黑板，重点结束
那么我们怎么样才能把直径上的边权改为 -1 呢？
同学，你知道吗？STL库里有一个东西，他叫做map,根据树的性质，两点之间的路径，有且只有一条，所以当两个点都是树的直径上的点时，连接他们的边一定是树的直径上的一条边，我们就可以这条边的权值改为 -1 啦
map
map是STL库一种东西(我也不知道算不算数据结构)
它形似map<int,bool>Mymap,它支持以前一个数为下标(也可以是字符或字符串)，返回后一个值，它的主要函数叫做，举个例子：
map<int,bool>Mymap;//定义一个叫Mymap的map
if(Mymap.count(x)==1)//判断x这个元素是否在map中,是返回1，否则返回0
…………；//一波操作
Mymap[x]=1;//将x这个元素加入Mymap中不知道这么说合不合适，其实map是非常好用的，常被我用来代替字符串Hash
那么问题又被我们简化了，我们现在只要求出直径上有那些点就可以了,这个时候就体现出了dfs的强大
我们需要定义一个fr数组来记录我们的直径上的点
代码(求树的直径上的点)
void dfs_for_D(int now,int father,int tar/*需要到的目标点*/){
if(flag_find_D==true) return;//记录是否已经找到了所有点
for(int i=linkk[now];i;i=e[i].nxt){
if(flag_find_D==true) return;
if(e[i].to==father) continue;
if(e[i].to==tar){
fr[now]=e[i].to;//记录这个点连向的下一个点
flag_find_D=true;
return;
}
fr[now]=e[i].to;
//如果这并不是需要的点，不用担心，他会在以后的dfs中被覆盖
dfs_for_D(e[i].to,now,tar);
if(flag_find_D==true) return;
}
}
dfs_for_D(start,0,end);//start,end分别为直径的起点，终点
然后，我们就把树的直径中的所有点存在了fr中 下面我们需要利用map记录下这些点，通过上面的代码，不难发现，fr数组的思想类似于邻接表，所以便历也与邻接表相似
for(int i=start;i!=end;i=fr[i])
__map[i]=1;//如果这个点在直径上，把他打上tag(__map是定义的map)但是，由于for循环的缘故，我们直径的最后一个节点并没有被打上标记，需要我们自己加:
__map[end]=1;现在，所有直径上的点都被我们打上了tag，我们只需要把连着这些点的边的权值修改就可以了，做法很简单
代码(修改权值)
for(int i=1;i<=N;++i)//遍历每一个点
if(__map.count(i)==1)//边的起点首先要被打上过标记
for(int j=linkk[i];j;j=e[j].nxt)//遍历这个点所衍生出的边
if(__map.count(e[j].to)==1)//终点也打上标记表示这就是直径上的点
e[j].value=-1;//修改权值然后，我们就成功地把这个图加工成了我们需要的东西，再求一遍树的直径就可以了，等等_注意要用树形dp求，因为这棵树此时已经有了负边权的边！！诶呦我去，这个卡了我好久，太菜了，没有办法
我们帮警察叔叔省下的路就是
2*(N-1)-(Dfront-1)-(Dafter-1)
=2*N-Dfront_Dafter因为在第二次求边权是的边的权值是 -1 所以第二个环的重边,在计算时已经从省下的路径中减去了，所以我们可以大胆地这么计算
奉献一波AC码(339ms(whithout O-2),5696kb)应该很少有人这么写吧
#include <bits/stdc++.h>
#define C getchar()
using namespace std;
const int maxn=100010;
inline int read(){
int x=0;char ch;bool flag=true;
for(;!isdigit(ch);ch=C) flag=ch=='-'?false:true;
for(;isdigit(ch);ch=C) x=(x<<3)+(x<<1)+(ch^48);
return flag?x:-x;
}//神仙快读
int N,K;
struct edge{
int nxt;
int to;
int value;
}e[maxn<<1]={};//邻接表,注意开两倍
int linkk[maxn]={};
int len,x,y,_max,id,Dfront,Dafter,start,end,fr[maxn]={},dis[maxn]={};
bool flag_find_D=false;
map<int,bool>__map;//定义一个map
void insert(int x,int y){
e[++len].to=y;
e[len].nxt=linkk[x];
e[len].value=1;
linkk[x]=len;
}
void dfs(int x,int father,int weight){
if(weight>=_max){
_max=weight;
id=x;
}
for(int i=linkk[x];i;i=e[i].nxt)
if(e[i].to!=father)
dfs(e[i].to,x,weight+e[i].value);
}//dfs求树的直径
void dfs_for_D(int now,int father,int tar){
if(flag_find_D==true) return;
for(int i=linkk[now];i;i=e[i].nxt){
if(flag_find_D==true) return;
if(e[i].to==father) continue;
if(e[i].to==tar){
fr[now]=e[i].to;
flag_find_D=true;
return;
}
fr[now]=e[i].to;
dfs_for_D(e[i].to,now,tar);
if(flag_find_D==true) return;
}
}//记录树的直径上的点
void Dp_to_Find_D_afther(int now,int father){
for(int i=linkk[now];i;i=e[i].nxt){
if(e[i].to==father) continue;
Dp_to_Find_D_afther(e[i].to,now);
Dafter=max(Dafter,dis[now]+dis[e[i].to]+e[i].value);
dis[now]=max(dis[now],dis[e[i].to]+e[i].value);
}
}//树形dp求树的直径
int main(){
N=read(),K=read();
for(int i=2;i<=N;++i){
x=read(),y=read();
insert(x,y);
insert(y,x);
}//建图
dfs(1,0,0);//第一次dfs(从一个你喜欢的节点开始)
start=id,_max=0;
dfs(start,0,0);//第二次dfs(从到你喜欢的节点的最远的哪一个节点开始)
Dfront=_max,end=id;//求出造第一条路时的树的直径——Dfront
if(K==1){
printf("%d",(2*(N-1)-Dfront+1));
return 0;
}//k==1时直接输出并退出(30分)
dfs_for_D(start,0,end);//记录直径——Dfront上的点
__map[end]=1;
__map[start]=1;
for(int i=start;i!=end;i=fr[i])
__map[i]=1;//给直径——Dfront上的点打上标记
for(int i=1;i<=N;++i)
if(__map.count(i)==1)
for(int j=linkk[i];j;j=e[j].nxt)
if(__map.count(e[j].to)==1)
e[j].value=-1;//修改边权
Dp_to_Find_D_afther(1,0);//树上dp求造第二条路时树的直径——Dafter(此时有负边权的边)
printf("%d",2*N-Dfront-Dafter);//k==2时输出并退出
return 0;
}