树

Phyllis_ · 2024-09-23 21:41:49 · 算法·理论

树

date : 2024.9.23

无根树

节点只有相邻关系而无父子关系

void dfs(int from,int x){
    for x 的所有相邻节点 y {
        if(y != from)//这个地方特别关注
            dfs(x,y);
    }
}
dfs(-1,x);

树的直径

树的直径可以存在多条

树的直径中间的节点为树的中心，如果直径为偶数，中间的两个节点都可以是树的中心，树的中心到其它点的最长路径最短

随机选取一个点，然后以这个点搜索距离最远的点 a，然后再以 a 搜索最远的点 b , a-b 即为直径

两次dfs/bfs求直径

优：可记录直径的路径，可计算出直径长度

缺：只适用于无负权边的树

//隐约雷鸣 阴霾天空 但盼风雨来 能留你在此
#include <bits/stdc++.h>
const int maxn = 1e5+10;
#define fsync ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
vector<int> eg[maxn];
int dis[maxn];
int pre[maxn];
void dfs(int x){
    for(auto y : eg[x]){
        if(y != pre[x]){
            pre[y] = x;
            dis[y] = dis[x]+1;
            dfs(y);
        }
    }
}
int main(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        eg[u].push_back(v);
        eg[v].push_back(u);
    }
    pre[1] = -1;
    dfs(1);
    int maxd = 0,idx = 0;
    for(int i = 1; i <= n; i++){
        if(dis[i] > maxd){
            idx = i,
            maxd = dis[i];
        }
    }
    memset(dis,0,sizeof(dis));
    memset(pre,0,sizeof(pre));
    pre[idx] = -1;
    dfs(idx);
    maxd = 0;
    for(int i = 1; i <= n; i++){
        maxd = max(maxd,dis[i]);
    }
    cout << maxd << endl;
    return 0;
}

求路径

void dfs_p(int x,int f,int e){
    if(tg == true) return ;
    for(int i = head[x]; ~i; i = eg[i].nxt){
        if(tg == true) return ;
        if(eg[i].to == f) continue;
        if(eg[i].to == e){
            tg = true;
            ft[x] = eg[i].to;
            return ;
        }
        ft[x] = eg[i].to;//里面存的就是节点
        dfs_p(eg[i].to,x,e);
        if(tg == true) return ;
    }
}
//起点 0 终点
//均用二次dfs求出了
dfs_p(s,0,e);

树形dp求直径

优：可求有负权边的树，可算出直径长度

缺：无法记录路径

~~死记硬背代码~~ 用一次dfs求

设 d[x] 表示从节点 x 出发走向以 x 为根的子树，能够到达的最远节点的距离，f[x] 表示经过任意点u 的最长路径长度

有 d[x] = max(d[y]+edge(x,y)(1 \le i \le t)

f[x] = max(d[y_i]+d[y_j]+edge(x,y_i)+edge(x,y_j) (1 \le j < i \le t)

void dp(int x){
    v[x] = 1;
    for(int i = head[x]; ~i; i = eg[i].nxt){
        int y = eg[i].to;
        if(vis[y]) continue;
        dp(y);
        ans = max(ans,d[x]+d[y]+eg[i].w);
        d[x] = max(d[x],d[y]+eg[i].w);
    } 
}

树的重心

对于无根树，删除节点 u 后得到两棵或更多棵互不连通的子树，其中最大子树的节点数最少

一棵树可能有 1 或 2 个重心

树的重心的性质：

当重心为根节点时，它底下每个子树的大小不大于整棵树大小的一半
重心到其他所有节点的距离和最小

//隐约雷鸣 阴霾天空 但盼风雨来 能留你在此
#include<cstdio>
#include <cmath>
#include <algorithm>
const int maxn = 5e4+10;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,cnt;
struct node{
    int to,nxt;
}eg[maxn<<1];
int head[maxn<<1];
void init(){
    for(int i = 0; i < maxn; i++){
        eg[i].nxt = -1,head[i] = -1;
    }
    cnt = 0;
}
void add(int u,int v){
    eg[cnt].nxt = head[u];
    eg[cnt].to = v;
    head[u] = cnt++;
}
int d[maxn],ans[maxn],num,maxnum = 1e9;
void dfs(int u,int fa){
    d[u] = 1;
    int tmp = 0;
    for(int i = head[u]; ~i; i = eg[i].nxt){
        int v = eg[i].to;
        if(v == fa) continue;
        dfs(v,u);
        d[u]+=d[v];
        tmp = max(d[v],tmp);
    }
    tmp = max(tmp,n-d[u]);
    //cout << u << " " << d[u] << " " << n-d[u] << " "<< tmp << endl;
    if(tmp < maxnum){ 
        num = 0;
        maxnum = tmp;
        ans[++num] = u;
    }else if(tmp == maxnum) ans[++num] = u;
    return ;
}
int main(){
    scanf("%d",&n);
    init();
    for(int i = 1; i < n; i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    sort(ans+1,ans+1+num);
    for(int i = 1; i <= num; i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

LCA(最近公共祖先)

对于两个节点 u , v ,找到一个树深度最大的祖先，多个节点的 LCA 可以转换成多次求两个节点 LCA 的形式

倍增法求LCA

时间复杂度 O(nlog_2n+mlog_2n)

Fst,

把 x 和 y 提到相同的深度，倍增跳，从大到小跳
dfs$ 时预处理 $fa[x][i] = fa[a[x][i-1]][i-1]
一共跳了2^{i-1} + 2^{i-1} = 2^i 步

特别的，fa[x][0] 是 x 的父节点

Snd.

当 $fa[x][i] = fa[y][i]$ 时，这是一个公共祖先，它的深度小于等于$LCA(x,y)$，这说明跳过头了，退回去换一个小的 $i-1$ 重新跳当 $fa[x][i] \ne fa[y][i]$ 时，更新 $x = fa[x][i]$ ，$y = fa[y][i]
最后肯定跳到离LCA差一层深度的地方，所以返回 fa[x][0]

void dfs(int u,int f){
    deep[u] = deep[f]+1;
    fa[u][0] = f;
    for(int i = 1; (1<<i) <= deep[u]; i++){
        fa[u][i] = fa[fa[u][i-1]][i-1];//※重要递推式子 
    }
    for(int i = head[u]; ~i; i = eg[i].nxt){
        if(eg[i].to != f){
            dfs(eg[i].to,u);
        }
    }
}
int LCA(int x,int y){
    //让x位于更低层，深度更大的位置
    if(deep[x] < deep[y]) swap(x,y);  
    //1.把x和y提到相同的深度 
    for(int i = 19; i >= 0; i--){//2^19 > 5e5+5;
        if(deep[x]-(1<<i) >= deep[y]) 
            x = fa[x][i];
    }
    if(x == y) return x;    
    //2.把x和y同步往上跳，找到LCA
    for(int i = 19; i >= 0; i--){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i],y = fa[y][i];
        }
    }
    return fa[x][0]; 
}

Tarjan求LCA

~~学不动了，不学了（bushi）~~

时间复杂度很好，并且无法优化 O(n+m)

LCA应用

求树上两点间的最短距离

dist(x,y) = deep[x] + deep[y] - 2 \times deep[LCA(x,y)]

树上差分

void dfs(int u,int pre){
    for(int i = head[u]; ~i; i = eg[i].nxt){
        int v = eg[i].to;
        if(v == pre) continue;
        dfs(v,u);
        dist[u] += dist[v];
    }
    ans = max(ans,dist[u]);
}
for(int i = 1; i <= k; i++){
    int s,t;
    cin >> s >> t;
    int l = LCA(s,t);
    dist[s]++,dist[fa[l][0]]--,dist[t]++,dist[l]--;
}
dfs(1,0);