第五章总结

二叉树

定义很重要，没错，我就默一遍吧。（最简单的不写）

　　　　结点的度：结点拥有的子树个数（分支数）；

　　　　祖先：根到该结点所经分支上的所有的结点；

　　　　树的度：树内结点度的最大值；

　　　　树的高度（深度）：树的最大层次；

　　然后是二叉树的性质，也很重要我也来一遍吧。

证明错了请指正！！！

　　学习笔记

树的dfs序（先序）

题目：https://cn.vjudge.net/contest/283912#problem/J

　　意思是给你一些属从关系，a b ，代表b 是a 的上属，你可以给一个人分配任务，他和他所有下属都要做那个任务，然后可以查询一个人现在在做什么任务，无分配就输出-1；

　　这题很容易想到并查集，但还可以用线段树做，通过懒惰标记来pushdowm任务，精髓是对每一个结点的子树dfs序编号，就把子树变成线性结构的一个区间了，从而可以很容易的通过递归更改任务。

　　代码：

  1 #include<iostream>
  2 #include<vector>
  3 #include<cstring>
  4 #include<stdio.h>
  5 using namespace std;
  6 #define pb push_back
  7 const int N = 50005;//员工最多有那么多个
  8 
  9 vector <int> ve[N];//就建立那么多的树，ve[他]表示他为经理的一颗树
 10 bool vis[N];//用于标记数组
 11 int index;//时间戳中间变量
 12 int sta[N],en[N];//结点dfs序的开始与结束
 13 
 14 typedef struct Node{
 15     int task,lazy;
 16 }Node;
 17 Node tree[N << 2];
 18 void dfs(int k)
 19 {
 20     sta[k]=++index;
 21     int len=ve[k].size();
 22     for(int i=0;i<len;i++)
 23         dfs(ve[k][i]);
 24     en[k]=index;
 25 }
 26 
 27 void pushdown(int root)
 28 {
 29     if(tree[root].lazy )//有懒惰标记
 30     {
 31         tree[root * 2 + 1].lazy =tree[root * 2 + 2].lazy =tree[root].lazy ;//将现在结点的懒惰标记下传
 32         tree[root * 2 + 1].task =tree[root * 2 + 2].task =tree[root].task ;//下属的任务和经理相同
 33         tree[root].lazy =0;//经理的懒标记清空
 34     }
 35 }
 36 
 37 int query(int root,int l,int r,int index)//根，左，右，index是x号员工开始的时间戳
 38 {
 39     if( l==r && l==index )
 40         return tree[root].task ;
 41     pushdown(root);//对于每一次查询，更新root下面的懒标记和任务
 42     int mid=(l+r)/2;
 43     if(index<=mid)
 44     {//答案在左边
 45         return query(root*2+1,l,mid,index);
 46     }
 47     else//答案在右边
 48         return query(root*2+2,mid+1,r,index);//!!!!!!!!!!!!!!!!
 49 }
 50 
 51 void update(int root ,int l,int r,int pl,int pr,int task)//pl，pr是x号员工对应下属树的区间左和右，将他们全部更新为task
 52 {
 53     if( r<pl || pr<l)
 54         return;
 55     if(l >= pl && r <= pr )
 56     {
 57         tree[root].lazy =1;
 58         tree[root].task =task;
 59         return ;
 60     }
 61     pushdown(root);//对于没进入上面两个if，都要下传本次经理的懒标记和任务
 62     int mid=( l + r ) /2;
 63     if(pl<=mid){
 64         update(root *2+1,l,mid,pl,pr,task);
 65     }
 66     if(pr>mid)
 67     {
 68         update(root *2+2,mid+1,r,pl,pr,task);
 69     }
 70 }
 71 
 72 int main()
 73 {
 74     int cnt=0;//用于输出case的数字
 75     int t;
 76     scanf("%d",&t);
 77     while(t--)
 78     {
 79         int n;
 80         cnt++;
 81         scanf("%d",&n);
 82         for(int i=1;i<=n;i++)
 83             ve[i].clear();//先初始化全部经理树
 84         memset(vis,false,sizeof(vis));//初始化vis为负一
 85         for(int i=0;i<n-1;i++)
 86         {
 87             int u,v;
 88             cin>>u>>v;
 89             vis[u]=true;//记录的是u，下属！
 90             ve[v].pb(u);//把u放入名字为v的动态数组，表示u是v的下属
 91         }
 92         index=0;
 93 
 94         for(int i=1;i<=n;i++)
 95         {
 96             if(!vis[i]){
 97                 dfs(i);
 98                 break;
 99             }
100         }
101         for(int i=1;i<(N<<2);i++)
102         {//初始化树的懒惰标记和任务
103             tree[i].task =-1;//一开始没有任务，要输出-1
104             tree[i].lazy =0;
105         }
106         printf("Case #%d:
",cnt);
107 
108         int M;
109         cin>>M;
110         while(M--)
111         {
112             char ch;
113             cin>>ch;
114             if(ch=='C'){//查询x号员工现在做的工作
115                 int x;
116                 cin>>x;
117                 cout<<query(1,1,n,sta[x])<<endl;
118             }
119             else{
120                 int x,y;
121                 scanf("%d %d",&x,&y);
122                 update(1,1,n,sta[x],en[x],y);//更新x的所有下属去做任务y
123             }
124         }
125     }
126     return 0;
127 }

目标：把主席树思想转化为代码，红黑树，字典树有时间搞搞。

　　 省赛前复习最小生成树，并查集，最短路径和深广搜。