Skip to content

Latest commit

 

History

History
322 lines (245 loc) · 8.3 KB

07-树.md

File metadata and controls

322 lines (245 loc) · 8.3 KB
Raw

树

倍增LCA

/*
首先dfs一遍找出所有节点的父亲fa和深度d
fa[rt] = -1;
*/

int st[maxn][20];  //n < (1<<20)

void initLCA(int n) {
    st[0][0] = -1;
    for (int i = 1; i <= n; i++) st[i][0] = fa[i];

    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= n; i++) {
            if (st[i][j - 1] < 0) st[i][j] = -1;
            else st[i][j] = st[st[i][j - 1]][j - 1];
        }
    }
}

int LCA(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    for (int i = 0; d[u] != d[v]; i++) {
        if ((d[u] - d[v]) >> i & 1) {
            u = st[u][i];
        }
    }
    if (u == v) return u;

    for (int i = 19; i >= 0; i--) {
        if (st[u][i] != -1 && st[v][i] != -1 && st[u][i] != st[v][i]) {
            u = st[u][i];
            v = st[v][i];
        }
    }
    return st[u][0];
}

LCA的个数

  • 结论：树上选取$n$个结点，两两之间取$LCA$，本质不同的$LCA$最多为$n-1$个
  • 证明：往已有的$n$个点中加入一个新点，最多增加一个新的本质不同的$LCA$，该$LCA$为新点与旧点的所有$LCA$中距离新点最近的$LCA$，然后数学归纳法。
  • 补充：选取的$n$个结点没有任何两点互相为祖先的话，必然有$n-1$个$LCA$，若有点互为祖先，依然可能有$n-1$个$LCA$。

LCA 与 DFS序

  • 结论：树上选取一个点集${S}$，点集中一定存在至少一对点对$(u, v)$使得$LCA(u,v)=LCA(S)$，且当$(u,v)$分别为点集${S}$中$DFS$序最小与最大时，该结论一定成立。
  • 该结论等价于：对于点对$(u,v)(DFN[u]<DFN[v])$，定点$u$和动点$v$的$LCA$随$v$的$DFS$序增大而不减，定点$v$和动点$u$的$LCA$随$u$的$DFS$序减小而不减。

点到链的最短距离（HDU 5296）

  • 题意：边权树上给出一个点集${S}$和一个点$u(u\notin S)$，从$S$中任选两个点$(x,y)$组成一条链，问组成的链离$u$的最短距离是多少。

  • 做法：从$S$中选点，从$DFS$序小于$u$的点中选出$DFS$序最大的一个点$x$，从$DFS$序大于$u$的点中选出$DFS$序最小的一个点$y$，若不存在这样的$x$或者$y$，则选取$DFS$序最小和最大的两个点作为$x$和$y$。求$u$到链$(x,y)$的距离。

  • 求值：$dis[i]$表示点$i$到根节点的距离，$ans=dis[u]-dis[lca(u,x)]-dis[lca(u,y)]+dis[lca(x,y)]$

点分治

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 20005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

struct edge {
    int to, val;
};
vector<edge> mp[maxn];

int mini, rt, totSZ;
int sz[maxn], dis[maxn];
bool vis[maxn];

int l, r, q[maxn];  //q为每次得到的距离合集

int n, ans; //ans记录合法点对

void getRT(int u, int pre) {    //每次调用 getRT() 前使 mini=inf, totSZ = sz[v];
    sz[u] = 1;
    int mxSub = 0;
    for (auto it: mp[u]) {
        int v = it.to;
        if (v == pre || vis[v]) continue;

        getRT(v, u);
        sz[u] += sz[v];
        mxSub = max(mxSub, sz[v]);
    }

    int mx = max(mxSub, totSZ - sz[u]);
    if (mx < mini) {
        mini = mx;
        rt = u;
    }
}

void getDIS(int u, int pre) {
    q[++r] = dis[u];
    for (auto it: mp[u]) {
        int v = it.to, val = it.val;
        if (v == pre || vis[v]) continue;
        dis[v] = dis[u] + val;
        getDIS(v, u);
    }
}

int calc(int u, int val) {
    l = 1, r = 0;
    dis[u] = val;
    getDIS(u, 0);

    //按照题意处理q

    return sum;
}

void dfs(int u) {
    vis[u] = true;
    ans += calc(u, 0);
    for (auto it: mp[u]) {
        int v = it.to, val = it.val;
        if (vis[v]) continue;

        ans -= calc(v, val);

        mini = inf;
        totSZ = sz[v];
        getRT(v, 0);
        dfs(rt);
    }
}

int main() {

    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            mp[i].clear();
            vis[i] = false;
        }
        ans = 0;

        for (int i = 1; i < n; i++) {
            int u, v, val;
            scanf("%d%d%d", &u, &v, &val);
            mp[u].push_back(edge{v, val});
            mp[v].push_back(edge{u, val});
        }

        mini = inf;
        totSZ = n;
        getRT(1, 0);
        dfs(rt);

        printf("%d\n", ans);
    }

    return 0;
}

异或最小生成树（CF 888G）

题面

给出$n$点和他们的权值$a_i$，连接点$i$与点$j$的边权值为$a_i\bigoplus a_j$，求最小生成树。

$Boruvka$算法

虽然我是按照$Kruskal$的思路解的这题，但看大部分题解都说是$Boruvka$，且我看代码和我没啥区别，姑且把这个偏门算法贴在这里。

  • 算法流程：对于每一个连通块，枚举其出边。取其最小出边，合并两个连通块。
  • 复杂度：每次合并联通块个数减少一半，$O(nlogn)$。

Solution

  • 将所有点权加入$0-1 Trie$中，$n$个点看成$n$个叶子结点，则连接两点$i,j$的边权值显然从$LCA(i,j)$开始计算贡献，考虑$Kruskal$，显然应该从最深的$LCA$开始连边。
  • 结论1：若一个$0-1 Trie$结点有$2$个儿子，则该结点必为某两叶子结点的$LCA$
  • 结论2：树上$n$个点两两取$LCA$，最多$n-1$个本质不同的$LCA$。（详情参考 数论相关$-LCA$的个数）
  • 推论：这颗$Trie$上最多$n-1$个点有$2$个儿子
  • $2$个儿子的结点实际相当于$0$儿子与$1$儿子分别为联通块，因为单个儿子子树内的点与本子树内的点相连一定优于与子树外的点相连。因此找到最短的一条连接两个联通块的边即可。
  • 找最短边的过程：枚举$0$儿子内的左端点，在$1$儿子内按$Trie$树遍历的方式找使异或值最小的右端点。
  • 时间复杂度：对于每个$2$儿子点，找最短边时枚举左端点的极限数量为其子树大小，在最大度为$2$的树上，$n$个不同点的子树大小和为$n+(n/2+n/2)+(n/4+n/4+n/4+n/4)+(n/8*8)...$即$O(nlogn)$，对每个左端点找右端点$O(logn)$，因此总复杂度$O(nlog^2 n)$。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 200005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

struct TrieNode {
    int son[2];
} trie[maxn * 30];
int tot = 0;
int L[maxn * 30], R[maxn * 30];

int a[maxn];

void newNode() {
    tot++;
    trie[tot].son[0] = 0;
    trie[tot].son[1] = 0;
}

void insert(int val, int id) {
    int now = 0;
    for (int i = 29; i >= 0; i--) {
        int ch = (val >> i) & 1;
        if (!trie[now].son[ch]) {
            newNode();
            trie[now].son[ch] = tot;
            L[tot] = id;
        }
        now = trie[now].son[ch];
        R[now] = id;
    }
}

int query(int now, int val, int d) {
    int ans = 1 << d;
	  d--;
    for (int i = d; i >= 0; i--) {
        int ch = (val >> i) & 1;
        if (trie[now].son[ch]) {
            now = trie[now].son[ch];
        } else {
            ans += (1 << i);
            now = trie[now].son[ch ^ 1];
        }
    }
    return ans;
}

ll dfs(int u, int d) {
    int x = trie[u].son[0];
    int y = trie[u].son[1];
    if (x && y) {
        int mini = (1 << 30);
        for (int i = L[x]; i <= R[x]; i++) {
            mini = min(mini, query(y, a[i], d));
        }
        return dfs(x, d - 1) + dfs(y, d - 1) + mini;
    } else if (x) {
        return dfs(x, d - 1);
    } else if (y) {
        return dfs(y, d - 1);
    } else {
        return 0;
    }
}

int main() {

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        insert(a[i], i);
    }
    L[0] = 1; R[0] = n;

    ll ans = dfs(0, 29);
    printf("%lld\n", ans);

    return 0;
}

树哈希

对于有根树，有两种较好的哈希方法，$prime_i$ 表示第 $i$ 个质数：

  • $f_u = 1 + \sum\limits_{v\in son_u} f_v\times prime_{sz_v}$
  • $f_u=\prod\limits_{v\in son_u} (f_v + prime_{sz_v})$

树哈希很容易发生冲突，最好直接上双哈希

对于无根树，找重心，一颗树的重心最多只有两个，分别比较即可

pll dfs(int u, int fa) {
    sz[u] = 1;
    pll ans = {1, 1};
    for (int v : G[u]) {
        if (v == fa || !vis[v]) continue;
        pll tmp = dfs(v, u);
        sz[u] += sz[v];
        ans.first += tmp.first * prime[sz[v]] % mod.first;
        ans.second *= (tmp.second + prime[sz[v]]) % mod.second;
        ans = ans % mod;
    }
    return ans;
}