Part 1 求一棵树的直径的长度
方法1：2遍DFS
1.任找一个点root，DFS找距离root最远的点x
2.以x为根节点，DFS找到距离x最远的点y
则x到y为树的一条直径
代码实现：
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,vv,w;
cin>>u>>vv>>w;
v[u].push_back((o){vv,w});
v[vv].push_back((o){u,w});
}
dfs(1,0);
cout<<maxn;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
struct o{
int to;
int val;
};
vector<o> v[500010];
int maxn=0;
int ans=0;
int rec;
void dfs1(int now,int lon,int fa){
if(maxn<lon){
maxn=lon;
rec=now;
}
for(int i=0;i<v[now].size();i++){
if(v[now][i].to==fa) continue;
dfs1(v[now][i].to,lon+v[now][i].val,now);
}
}
void dfs2(int now,int lon,int fa){
if(ans<lon){
ans=lon;
}
for(int i=0;i<v[now].size();i++){
if(v[now][i].to==fa) continue;
dfs2(v[now][i].to,lon+v[now][i].val,now);
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,vv,w;
cin>>u>>vv>>w;
v[u].push_back((o){vv,w});
v[vv].push_back((o){u,w});
}
dfs1(1,0,0);
dfs2(rec,0,0);
cout<<ans;
return 0;
}
方法2：树形DP
设DP[i]和f[i]表示以点i为根节点的子树的最长链和次长链取max(dp[i]+f[i])
代码实现：
#include<bits/stdc++.h>
using namespace std;
int n;
int maxn=0;
struct o{
int to;
int val;
};
vector<o> v[500010];
int dp[500010];
int f[500010];
void dfs(int now,int fa){
//cout<<now<<endl;
dp[now]=f[now]=0;
for(int i=0;i<v[now].size();i++){
if(v[now][i].to==fa) continue;
dfs(v[now][i].to,now);
int t=dp[v[now][i].to]+v[now][i].val;
if(t>dp[now]){
f[now]=dp[now];
dp[now]=t;
}
else if(t>f[now]){
f[now]=t;
}
}
maxn=max(maxn,dp[now]+f[now]);
return;
}
例题1：
P3629 [APIO2010] 巡逻
首先，显然不加边时每条边需要经过2次，一次过去，一次回来
然后，加1条边时，形成1个环，环上每条边只需要经过1次，相比没加之前每条边要少1次，显然我们只需要让环上的边最多，也就是找直径，最后计算答案先2* (n-1)是不加边的路径数，减去直径上的边数，最后不要忘了加上1，也就是加的那一条边，轻松拿到三十分
代码实现：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int maxn=0;
struct o{
int to;
int val;
};
vector<o> v[500010];
int dp[500010];
int f[500010];
int cur[500010];
int cnt=0;
void dfs(int now,int fa){
//cout<<now<<endl;
dp[now]=f[now]=0;
for(int i=0;i<v[now].size();i++){
if(v[now][i].to==fa) continue;
dfs(v[now][i].to,now);
int t=dp[v[now][i].to]+v[now][i].val;
if(t>dp[now]){
f[now]=dp[now];
dp[now]=t;
}
else if(t>f[now]){
f[now]=t;
}
}
maxn=max(maxn,dp[now]+f[now]);
return;
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
int u,vv,w=1;
cin>>u>>vv;
v[u].push_back((o){vv,w});
v[vv].push_back((o){u,w});
}
dfs(1,0);
if(k==1){
cout<<2*(n-1)-maxn+1;
}
return 0;
}
再考虑K=2，还要加一条边，那是次长的那一条吗？不一定，因为如果两条中边有交集，手推发现交集那部分边又要走两遍了，因此我们可以把第一边扫过的边的边权改成-1，这样就可以加上重复的边数
代码实现：
#include<bits/stdc++.h>
using namespace std;
template<typename type>
void read(type &x){
type f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
const int N=1e5+7;
struct node{
int to,w,next;
}e[N*2];
int head[N],cnt;
void add(int a,int b,int c){
e[++cnt].to=b;
e[cnt].next=head[a];
head[a]=cnt;
e[cnt].w=1;
}
int dis[N],vis[N],l1,l2,n,k,point,f[N],d[N],v[N];
int ans=0;
void bfs(int x,int ck){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int >q;
q.push(x);
vis[x]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=e[i].next){
int y=e[i].to;
if(!vis[y]){
vis[y]=1;
dis[y]=dis[now]+e[i].w;
q.push(y);
if(ck)f[y]=now;
}
}
}
for(int i=1;i<=n;i++){
if(ans<dis[i])ans=dis[i],point=i;
}
}
void change(int a){
while(f[a]){
int fa=f[a];
for(int i=head[fa];i;i=e[i].next){
if(e[i].to==a){
e[i].w=-1;
break;
}
}
for(int i=head[a];i;i=e[i].next){
if(e[i].to==fa){
e[i].w=-1;
break;
}
}
a=fa;
}
}
void dp(int x){
v[x]=1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(v[y])continue;
dp(y);
ans=max(ans,dis[x]+dis[y]+e[i].w);
dis[x]=max(dis[x],dis[y]+e[i].w);
}
}
int main(){
read(n);read(k);
for(int i=1;i<n;i++){
int a,b;
read(a);read(b);
add(a,b,1);
add(b,a,1);
}
if(k==1){
bfs(1,0);
bfs(point,0);
printf("%d",2*n-dis[point]-1);
}
else{
bfs(1,0);
bfs(point,1);
l1=dis[point];
change(point);
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
ans=0;
dp(1);
printf("%d",2*n-ans-l1);
}
return 0;
}