2017.8.14 树的基础运用课的小结

一、知识点

1.树的结构：由n个点n-1条边组成的图，比较常见的是二叉树.

2.树的遍历：分为前序遍历、中序遍历和后序遍历，前序遍历的访问顺序：中左右。中序遍历的访问顺序：左中右。后序遍历的访问顺序：左右中。

3.DFS 序：将一棵树按照前序遍历得到的给每个节点编号的一种顺序,它可以将一棵子树变成一段完整的区间方便处理.

4.线段树：一般是为了加快区间操作，多做题目就会有体会.

二、例题

例1：noip2014联合权值：传送门

分析：首先考虑怎么枚举出两个距离为2的边，难道是一对一对枚举吗？其实不是，可以发现，如果我们从一个点走向另外一个点i,再变个方向从原来的点走到另外一个点j,那么i和j的距离就为2，所以我们每次枚举中间点就好了，最大的联合权值的处理方法是每次枚举中间节点记录下走一步的最大节点和次大节点，乘一下就是以当前点为中心点的最大的联合权值了，然后把所有求出来的取一个max就好了。

至于怎么求联合权值的和，我们还是拿中心点来考虑，假设这个点走一步的所有节点的权值和为p,那么对于每一个走一步得到的节点i,这个节点的贡献就是i*(p-i),因为它仅仅不和自己相乘，这样就得到了问题的答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200010,mod = 10007;

int n,w[maxn],tot,head[maxn],nextt[maxn * 2],to[maxn * 2],sum,max1,max2,ans1,ans2;

void add(int a, int b)
{
    to[++tot] = b;
    nextt[tot] = head[a];
    head[a] = tot;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++)
    {
        max1 = max2 = -1;
        sum = 0;
        for (int j = head[i]; j; j = nextt[j])
        {
            int temp = w[to[j]];
            sum += temp;
            sum %= mod;
            if (temp > max1)
            {
                max2 = max1;
                max1 = temp;
            }
            else if (temp > max2)
                max2 = temp;
        }
        ans2 = max(ans2, max1 * max2);
        for (int j = head[i];j;j = nextt[j])
        {
            ans1 += (w[to[j]] * (sum - w[to[j]])) % mod;
            ans1 %= mod;
        }
    }
    ans1 = (ans1 + mod) % mod;
    printf("%d %d
", ans2, ans1);

    return 0;
}

例2：bzoj1369[Baltic2003]Gem

题目描述

给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

输入

先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连

输出

最小的总权值

样例输入

10 7 5 1 2 1 7 8 9 4 1 9 7 5 6 10 2 9 3

样例输出

分析：这道题一看就是树形dp题，因为无法搜索，没有更好的办法了,那么我们怎么dp呢？

考虑到对答案有影响的就是节点和节点的权值，那么我们可以假设f[i][j]表示在以i为根节点的子树中,i的权值为j的总权值，很容易得到状态转移方程式f[i][j] = Σmin{f[k][l]},其中，k是i的儿子，l≠j,只是，这个算法复杂度似乎是O(n^2)的啊，10000怎么跑得过，其实根据打表可以证明，只会出现3种不同的权值，我们每次枚举到3就好了。不过还有一个更靠谱的结论：最多有logn个权值，每次枚举到logn即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n,head[10010],to[20010],nextt[20010],tot,f[10010][5],ans = 1000000000;

void add(int x, int y)
{
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

void dfs(int u, int from)
{
    for (int i = 1; i <= 3; i++)
        f[u][i] = i;
    for (int i = head[u]; i + 1; i = nextt[i])
    {
        int v = to[i];
        if (v != from)
        {
            dfs(v, u);
            for (int j = 1; j <= 3; j++)
            {
                int minn = 100000000;
                for (int k = 1; k <= 3; k++)
                {
                    if (k != j)
                    minn = min(minn, f[v][k]);
                }
                f[u][j] += minn;
            }
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    for (int i = 1; i <= 3; i++)
        ans = min(ans, f[1][i]);
    printf("%d
", ans);

    return 0;
}

例3：

3306: 树

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 597 Solved: 185 [Submit][Status][Discuss]

Description

给定一棵大小为 n 的有根点权树,支持以下操作: 　　• 换根　　• 修改点权　• 查询子树最小值

Input

　　第一行两个整数 n, Q ,分别表示树的大小和操作数。　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。　　接下来 m 行,为以下格式中的一种: 　　• V x y表示把点x的权改为y 　　• E x 表示把有根树的根改为点 x 　　• Q x 表示查询点 x 的子树最小值

Output

　　对于每个 Q ,输出子树最小值。

Sample Input

3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1

Sample Output

1
2
3
4

HINT

　　对于 100% 的数据:n, Q ≤ 10^5。

分析：这道题目对我这种蒟蒻来说还是非常难的。

如果没有换根操作我们能怎么做呢？一般而言，对于子树的操作，我们都可以转换成字典序操作，因为一棵子树对应着一个完整的区间，而对于区间的操作，我们有很多优化方式，一般可以采用线段树维护何种操作，所以如果只有修改操作和查询操作，那么就相当于在一棵线段树上进行单点修改和区间查询。具体该怎么做呢？我们先用一次dfs求出dfs序，记录每个节点进入子树的时间和出来的时间，那么这两个时间就构成了一个区间，这个区间就是以这个节点为根的子树的dfs序，然后的转换有点麻烦，我们先记录一下每个节点的编号i的权值:va[i],然后记录dfs序是j的节点的编号：jilu[j],建线段树的时候每次都要用va[jilu[l]],这个l其实就是dfs序的一个值，因为我们的线段树就是对dfs序进行操作.之后的修改和查询就是正常的线段树操作了.

如果有换根操作我们该怎么办呢？首先可以肯定一点：我们绝对不能真的照它这么做去换根，因为每次换根都可能会移动n个节点，复杂度是不敢想象的，那么我们先只交换根，不对树进行其它的任何操作，那么这样就会对查询操作有影响，而修改操作可以照样进行。那么查询操作该怎么进行呢？如果查询的是根节点，直接O(1)输出整棵线段树的第一层就好了，现在考虑考虑根换成 x、询问 y 子树最小值的情况，显然，如果x是y的祖先，那么对查询操作一点影响都没有，因为y的子树还是那样，不会动，如果y是x的祖先就麻烦了，画个图，分析一下，能得出结论：除了 y 向 x 方向的一棵子树以外都是询问对象，为了求出这一棵子树，我们将x向上跳，直到跳到距离y最近的位置-----y下面一层，我们利用dfs序对这个位置两边进行查询合并一下答案就可以了，不过要怎么样才能快速的跳呢？倍增！就这么解决了这道题.复杂度=线段树+dfs序=O(q*logn + n).可以完美A掉此题！

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 int n, q,head[100010],to[100010],nextt[100010],tot,va[100010],l[100010],r[100010],deep[100010],cnt,root;
 10 int fa[100010][20],minn[500010],jilu[100010];
 11 
 12 void add(int x, int y)
 13 {
 14     to[tot] = y;
 15     nextt[tot] = head[x];
 16     head[x] = tot++;
 17 }
 18 
 19 void dfs(int u,int d)
 20 {
 21     deep[u] = d;
 22     l[u] = ++cnt;
 23     jilu[cnt] = u;
 24     for (int i = head[u]; i + 1; i = nextt[i])
 25     {
 26         int v = to[i];
 27         fa[v][0] = u;
 28         dfs(v, d + 1);
 29     }
 30     r[u] = cnt;
 31 }
 32 
 33 void update(int o)
 34 {
 35     minn[o] = min(minn[o * 2], minn[o * 2 + 1]);
 36 }
 37 
 38 void build(int o, int l, int r)
 39 {
 40     if (l == r)
 41     {
 42         minn[o] = va[jilu[l]];
 43         return;
 44     }
 45     int mid = (l + r) >> 1;
 46     build(o * 2, l, mid);
 47     build(o * 2 + 1, mid + 1, r);
 48     update(o);
 49 }
 50 
 51 void gengxin(int o, int x, int v, int l, int r)
 52 {
 53     if (l == r)
 54     {
 55         minn[o] = v;
 56         return;
 57     }
 58     int mid = (l + r) >> 1;
 59     if (x <= mid)
 60         gengxin(o * 2, x, v, l, mid);
 61     else
 62         gengxin(o * 2 + 1, x, v, mid + 1, r);
 63     update(o);
 64 }
 65 
 66 int query(int o, int l, int r, int x, int y)
 67 {
 68     if (x <= l && r <= y)
 69         return minn[o];
 70     int res = 1000000000, mid = (l + r) >> 1;
 71     if (x <= mid)
 72         res = min(res, query(o * 2, l, mid, x, y));
 73     if (y > mid)
 74         res = min(res, query(o * 2 + 1, mid + 1, r, x, y));
 75     return res;
 76 }
 77 
 78 int main()
 79 {
 80     memset(head, -1, sizeof(head));
 81     scanf("%d%d", &n, &q);
 82     for (int i = 1; i <= n; i++)
 83     {
 84         int f, v;
 85         scanf("%d%d", &f, &v);
 86         if (f)
 87             add(f, i);
 88         va[i] = v;
 89     }
 90     root = 1;
 91     dfs(1,1);
 92     for (int j = 1; j <= 17; j++)
 93         for (int i = 1; i <= n; i++)
 94             fa[i][j] = fa[fa[i][j - 1]][j - 1];
 95     build(1, 1, n);
 96     while (q--)
 97     {
 98         char s[5];
 99         int x;
100         scanf("%s%d", s, &x);
101         if (s[0] == 'V')
102         {
103             int t;
104             scanf("%d", &t);
105             gengxin(1, l[x], t,1,n);
106         }
107         else
108             if (s[0] == 'E')
109                 root = x;
110             else
111             {
112                 if (root = x)
113                     printf("%d
", minn[1]);
114                 else
115                 {
116                     if (l[x] <= l[root] && r[x] >= r[root])
117                     {
118                         int y = root, d = deep[root] - deep[x] - 1;
119                         for (int i = 16; i >= 0; i--)
120                             if (d & (1 << i))
121                                 y = fa[y][i];
122                         printf("%d
", min(query(1, 1, n, 1, l[y] - 1), query(1, 1, n, r[y] + 1, n)));
123                     }
124                     else
125                         printf("%d
", query(1, 1, n, l[x], r[x]));
126                 }
127             }
128     }
129 
130     return 0;
131 }

总结：对区间的操作我们都可以尝试利用线段树或树状数组来优化，一般有关树的区间问题都是依靠dfs序+线段树来解决的。如果一次操作要对一棵树的很多地方进行更改，我们可以先记录下这次操作，等到它出现影响的时候再分类讨论！