题目描述
树形dp求树的路径并记录路径
样例
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
手段
存储手段
开一个数组,存储某点的下一点边号。
sa[点号] = 下一条边的边号,注意体会一下和加边法的区别
循环方法
for(int i = sa1[ans_i]; ~i; i = sa1[e[i]]){
//
}
树的特性
dfs时用fa存储父节点放置反复遍历
一次改一对边
i, i ^ 1
注意次长路径是先次长再最长
for(int i = sa2[ans_i]; ~i; i = sa1[e[i]]){ // 次长后最长
// cout << i << " " << (i ^ 1) << endl;
w[i] = w[i ^ 1] = -1;
}
完整代码
详细证明其它题解很多,想法还是挺精妙的,记录路径的方法和一些其它题相似但不完全一样,一些细节还是思考了一会的。
// 2 * (n - 1) + 1 - L1 + (1 - L2)(if k == 2)
// 其中L1和L2路径重叠反而要走两次,因此可以把L1边权变负
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 2 * N;
int n, k, ans, ans_i;
int idx, h[N], ne[M], e[M], w[M];
int sa1[N], sa2[N];
void add(int a, int b, int c){
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++;
}
int dfs(int u, int fa){
int d1 = 0, d2 = 0; // 最长, 次长
for(int i = h[u]; ~i ; i = ne[i]){
int j = e[i];
if(j == fa) continue;
int d = dfs(j, u) + w[i];
if(d > d1) d2 = d1, d1 = d, sa2[u] = sa1[u], sa1[u] = i;
else if(d > d2) d2 = d, sa2[u] = i;
}
if(ans < d1 + d2){
ans = d1 + d2;
ans_i = u;
}
return d1;
}
int main(){
memset(h, -1, sizeof h);
memset(sa1, -1, sizeof sa1);
memset(sa2, -1, sizeof sa2);
cin >> n >> k;
for(int i = 0; i < n - 1; i ++ ){
int a, b;
cin >> a >> b;
add(a, b, 1);
add(b, a, 1);
}
dfs(1, -1);
if(k == 1){
cout << 2 * n - 1 - ans << endl;
return 0;
}
int ans_k1 = 2 * n - 1 - ans;
// k == 2
for(int i = sa1[ans_i]; ~i; i = sa1[e[i]]){
w[i] = w[i ^ 1] = -1;
}
for(int i = sa2[ans_i]; ~i; i = sa1[e[i]]){ // 次长后最长
w[i] = w[i ^ 1] = -1;
}
ans = 0;
dfs(1, -1);
cout << ans_k1 - ans + 1 << endl;
return 0;
}