博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
树链剖分
阅读量：6931 次
发布时间：2019-06-27

本文共 55966 字，大约阅读时间需要 186 分钟。

1、hdu 3966 Aragorn's Story

　　题意：敌人有n个帐篷，每个帐篷有初始人数，两两之间只有一条路径。现在进行q次操作，可以把c1到c2路径上的所有帐篷人数都加上或减去一个值，或者询问某个帐篷当前人数。

　　思路：树链剖分模板题，线段树，点权，区间更新，单点查询。

1 #include
      
         2 #include
       
          3 using namespace std;  4 const int maxn = 50000 + 10;  5   6 /*-------树链剖分·启-------*/  7   8 int siz[maxn];//size[i]:以i为根的子树结点个数  9 int top[maxn];//保存结点i所在链的顶端结点 10 int son[maxn];//保存i的重儿子 11 int dep[maxn];//保存结点i的层次（深度） 12 int father[maxn];//保存结点i的父亲结点 13 int nid[maxn];//保存树节点剖分后的对应新编号 14 int oid[maxn];//保存新编号对应在剖分的树中的结点（与nid相反） 15 int cnt = 0;//重编号 16 int val[maxn];//结点值 17 struct EDGE 18 { 19     int from, to, next; 20     EDGE(int ff = 0, int tt = 0, int nn = 0) :from(ff), to(tt), next(nn) {} 21 }edge[maxn * 2]; 22 int Head[maxn], totedge = 0; 23 void addEdge(int from, int to) 24 { 25     edge[totedge] = EDGE(from, to, Head[from]); 26     Head[from] = totedge++; 27     edge[totedge] = EDGE(to, from, Head[to]); 28     Head[to] = totedge++; 29 } 30 void INIT() 31 { 32     memset(Head, -1, sizeof(Head)); 33     totedge = 0; 34  35     memset(son, -1, sizeof(son)); 36     memset(siz, 0, sizeof(siz)); 37     memset(father, 0, sizeof(father)); 38     memset(top, 0, sizeof(top)); 39     memset(dep, 0, sizeof(dep)); 40     cnt = 0; 41 } 42  43 void dfs1(int u, int fa, int layer) 44 { 45     dep[u] = layer; 46     father[u] = fa; 47     siz[u] = 1; 48     for (int i = Head[u]; i != -1; i = edge[i].next) 49     { 50         int v = edge[i].to; 51         if (v != fa) 52         { 53             dfs1(v, u, layer + 1); 54             siz[u] += siz[v]; 55             if (son[u] == -1 || siz[v] > siz[son[u]]) 56             { 57                 son[u] = v; 58             } 59         } 60     } 61 } 62  63 void dfs2(int u, int Hson) 64 {
    //Hson,重儿子 65     top[u] = Hson; 66     nid[u] = ++cnt; 67     oid[cnt] = u; 68     if (son[u] == -1) return; 69     dfs2(son[u], Hson);//先将当前重链重编号 70     for (int i = Head[u]; i != -1; i = edge[i].next) 71     {
    //对不在重链上的点，自己作为子树的重链起点重编号 72         int v = edge[i].to; 73         if (v != son[u] && v != father[u]) dfs2(v, v); 74     } 75 } 76 /*-------线段树·启————*/ 77 struct treenode 78 { 79     int l, r; 80     long long v, tmp; 81     treenode(int ll = 0, int rr = 0, long long vv = 0, long long tt = 0) :l(ll), r(rr), v(vv), tmp(tt) {} 82 }tree[maxn * 4]; 83  84 void BuildTree(int root, int l, int r) 85 { 86     tree[root].l = l, tree[root].r = r; 87     tree[root].tmp = 0; 88     if (l == r) 89     { 90         tree[root].v = val[oid[l]]; 91         return; 92     } 93     int mid = (l + r) / 2; 94     BuildTree(root * 2, l, mid); 95     BuildTree(root * 2 + 1, mid + 1, r); 96     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v; 97 } 98 void Pushdown(int root) 99 {100     int lson = root * 2, rson = root * 2 + 1;101     if (tree[root].tmp)102     {103         tree[lson].v += (tree[lson].r - tree[lson].l + 1)*tree[root].tmp;104         tree[rson].v += (tree[rson].r - tree[rson].l + 1)*tree[root].tmp;105         tree[lson].tmp += tree[root].tmp;106         tree[rson].tmp += tree[root].tmp;107         tree[root].tmp = 0;108     }109 }110 void PushUp(int root)111 {112     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;113 }114 void Update(int root, int l, int r, int add)115 {116     if (tree[root].r
        
         r) return;117     if (l <= tree[root].l&&tree[root].r <= r)118     {119         tree[root].tmp += add;120         tree[root].v += add * (tree[root].r - tree[root].l + 1);121         return;122     }123     Pushdown(root);124     int mid = (tree[root].r + tree[root].l) / 2;125     if (l <= mid)Update(root * 2, l, r, add);126     if (r>mid)Update(root * 2 + 1, l, r, add);127     PushUp(root);128 }129 130 long long Query(int root, int l, int r)131 {132     if (tree[root].r
         
          r) return 0;133     if (l <= tree[root].l&&tree[root].r <= r)134     {135         return tree[root].v;136     }137     Pushdown(root);138     long long tsum = Query(root * 2, l, r) + Query(root * 2 + 1, l, r);139     PushUp(root);140     return tsum;141 }142 /*-------线段树·终————*/143 144 long long Query_length(int x, int y)145 {
    //查询结点x到y路径上所有结点值之和146     long long ans = 0;147     int fx = top[x], fy = top[y];148     while (fx != fy)149     {150         if (dep[fx] >= dep[fy])151         {152             ans += Query(1, nid[fx], nid[x]);//在一条重链上的值用线段树维护、查询153             x = father[fx];154             fx = top[x];155         }156         else157         {158             ans += Query(1, nid[fy], nid[y]);159             y = father[fy];160             fy = top[y];161         }162     }163     //此时x与y已经在一条重链上，而重链上的编号都是连续的164     if (x != y)165     {166         if (nid[x] < nid[y])167         {168             ans += Query(1, nid[x], nid[y]);169         }170         else171         {172             ans += Query(1, nid[y], nid[x]);173         }174     }175     else ans += Query(1, nid[x], nid[y]);176     return ans;177 }178 179 void Update_path(int x, int y, int add)180 {
    //将x到y路径上所有结点的值都加上add181     int fx = top[x], fy = top[y];182     while (fx != fy)183     {184         if (dep[fx] >= dep[fy])185         {186             Update(1, nid[fx], nid[x], add);187             x = father[fx];188             fx = top[x];189         }190         else191         {192             Update(1, nid[fy], nid[y], add);193             y = father[fy];194             fy = top[y];195         }196     }197     if (x != y)198     {199         if (nid[x] < nid[y]) Update(1, nid[x], nid[y], add);200         else Update(1, nid[y], nid[x], add);201     }202     else Update(1, nid[x], nid[y], add);203 }204 /*-------树链剖分·终-------*/205 206 int main()207 {208     int n, m, p;209     while (~scanf("%d%d%d", &n, &m, &p))210     {211         INIT();212         for (int i = 1; i <= n; i++) scanf("%d", &val[i]);213         for (int i = 1; i <= m; i++)214         {215             int from, to;216             scanf("%d%d", &from, &to);217             addEdge(from, to);218         }219         dfs1(1, 1, 1);220         dfs2(1, 1);221         BuildTree(1, 1, n);222         char s[10];223         for (int i = 1; i <= p; i++)224         {225             scanf("%s", s);226             int c1, c2, k, c;227             switch (s[0])228             {229             case 'I':230                 scanf("%d%d%d", &c1, &c2, &k);231                 Update_path(c1, c2, k);232                 break;233             case 'D':234                 scanf("%d%d%d", &c1, &c2, &k);235                 Update_path(c1, c2, -k);236                 break;237             case 'Q':238                 scanf("%d", &c);239                 printf("%lld\n", Query(1, nid[c], nid[c]));240                 break;241             }242         }243     }244     return 0;245 }
View Code

2、HYSBZ - 2243 染色

　　题意：

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
　　思路：
树链剖分+线段树，点权，区间更新+区间查询，分段。线段树应当记录[l,r]中颜色段数量以及左右边界颜色。 
1 #include
       
          2 #include
        
           3 #include
         
            4 using namespace std;  5 const int maxn = 100000+ 10;  6   7 /*-------树链剖分·启-------*/  8   9 int siz[maxn];//size[i]:以i为根的子树结点个数 10 int top[maxn];//保存结点i所在链的顶端结点 11 int son[maxn];//保存i的重儿子 12 int dep[maxn];//保存结点i的层次（深度） 13 int father[maxn];//保存结点i的父亲结点 14 int nid[maxn];//保存树节点剖分后的对应新编号 15 int oid[maxn];//保存新编号对应在剖分的树中的结点（与nid相反） 16 int cnt = 0;//重编号 17 int val[maxn];//结点值 18 struct EDGE 19 { 20     int from, to, next; 21     EDGE(int ff = 0, int tt = 0, int nn = 0) :from(ff), to(tt), next(nn) {} 22 }edge[maxn * 2]; 23 int Head[maxn], totedge = 0; 24 void addEdge(int from, int to) 25 { 26     edge[totedge] = EDGE(from, to, Head[from]); 27     Head[from] = totedge++; 28     edge[totedge] = EDGE(to, from, Head[to]); 29     Head[to] = totedge++; 30 } 31 void INIT() 32 { 33     memset(Head, -1, sizeof(Head)); 34     totedge = 0; 35  36     memset(son, -1, sizeof(son)); 37     cnt = 0; 38 } 39  40 void dfs1(int u, int fa, int layer) 41 { 42     dep[u] = layer; 43     father[u] = fa; 44     siz[u] = 1; 45     for (int i = Head[u]; i != -1; i = edge[i].next) 46     { 47         int v = edge[i].to; 48         if (v != fa) 49         { 50             dfs1(v, u, layer + 1); 51             siz[u] += siz[v]; 52             if (son[u] == -1 || siz[v] > siz[son[u]]) 53             { 54                 son[u] = v; 55             } 56         } 57     } 58 } 59  60 void dfs2(int u, int Hson) 61 {
     //Hson,重儿子 62     top[u] = Hson; 63     nid[u] = ++cnt; 64     oid[cnt] = u; 65     if (son[u] == -1) return; 66     dfs2(son[u], Hson);//先将当前重链重编号 67     for (int i = Head[u]; i != -1; i = edge[i].next) 68     {
     //对不在重链上的点，自己作为子树的重链起点重编号 69         int v = edge[i].to; 70         if (v != son[u] && v != father[u]) dfs2(v, v); 71     } 72 } 73 /*-------线段树·启————*/ 74 struct treenode 75 { 76     int l, r; 77     int v, l_color, r_color; 78     int delay; 79     treenode(int ll = 0, int rr = 0,int vv = 0, int lc = 0,int rc=0,int dd=0) :l(ll), r(rr), v(vv),l_color(lc),r_color(rc),delay(dd){} 80 }tree[maxn * 4]; 81  82 void PushUp(int root) 83 { 84     int lson = root * 2, rson = root * 2 + 1; 85     tree[root].v = tree[lson].v + tree[rson].v; 86     if (tree[lson].r_color == tree[rson].l_color) tree[root].v--; 87     tree[root].l_color = tree[lson].l_color, tree[root].r_color = tree[rson].r_color; 88 } 89  90 void BuildTree(int root, int l, int r) 91 { 92     tree[root].l = l, tree[root].r = r; 93     tree[root].delay = 0; 94     if (l == r) 95     { 96         tree[root].v = 1; 97         tree[root].l_color=tree[root].r_color = val[oid[l]]; 98         return; 99     }100     int mid = (l + r) / 2;101     BuildTree(root * 2, l, mid);102     BuildTree(root * 2 + 1, mid + 1, r);103     PushUp(root);104 }105 106 void PushDown(int root)107 {108     int lson = root * 2, rson = root * 2 + 1;109     if (tree[root].delay)110     {111         tree[lson].v = tree[rson].v = 1;112         tree[lson].l_color = tree[lson].r_color = tree[root].delay;113         tree[rson].l_color = tree[rson].r_color = tree[root].delay;114         tree[lson].delay = tree[rson].delay = tree[root].delay;115         tree[root].delay = 0;116     }117 }118 119 void Update(int root, int l, int r, int nc)120 {121     if (tree[root].r
          
           r) return;122     if (l <= tree[root].l&&tree[root].r <= r)123     {124         tree[root].delay = nc;125         tree[root].l_color = tree[root].r_color = nc;126         tree[root].v =1;127         return;128     }129     PushDown(root);130     int mid = (tree[root].r + tree[root].l) / 2;131     if (l <= mid)Update(root * 2, l, r, nc);132     if (r>mid)Update(root * 2 + 1, l, r, nc);133     PushUp(root);134 }135 136 int Query(int root, int l, int r,int&rcolor)137 {138     if (tree[root].r
           
            r) return 0;139     if (l <= tree[root].l&&tree[root].r <= r)140     {141         if (rcolor == tree[root].l_color)142         {143             rcolor = tree[root].r_color;144             return tree[root].v - 1;145         }146         else147         {148             rcolor = tree[root].r_color;149             return tree[root].v;150         }151     }152     PushDown(root);153     int mid = (tree[root].l + tree[root].r) / 2;154     int ans = 0;155     if (l <= mid) ans += Query(root * 2, l, r, rcolor);156     if (r > mid) ans += Query(root * 2 + 1, l, r, rcolor);157     PushUp(root);158     return ans;159 }160 161 int Query_color(int root, int pos ,char flag)162 {
     //查询某个分段最左或最右的颜色163     if (tree[root].l == pos&&flag=='l')164     {165         return tree[root].l_color;166     }167     else if (tree[root].r == pos && flag == 'r')168     {169         return tree[root].r_color;170     }171     PushDown(root);172     int mid = (tree[root].l + tree[root].r) / 2;173     int ans = 0;174     if (pos <= mid) ans = Query_color(root * 2, pos,flag);175     else ans = Query_color(root * 2 + 1, pos,flag);176     PushUp(root);177     return ans;178 }179 180 181 /*-------线段树·终————*/182 183 int Query_length(int x, int y)184 {
     //查询结点x到y路径上颜色段数185     int ans = 0;186     int fx = top[x], fy = top[y];187     while (fx != fy)188     {189         if (dep[fx] >= dep[fy])190         {191             int rcolor = -1;192             ans += Query(1, nid[fx], nid[x],rcolor);//在一条重链上的值用线段树维护、查询193             int tlcolor = Query_color(1, nid[fx], 'l');194             x = father[fx];195             fx = top[x];196             int trcolor = Query_color(1, nid[x], 'r');197             if (trcolor ==tlcolor) ans--;198         }199         else200         {201             int rcolor = -1;202             ans += Query(1, nid[fy], nid[y],rcolor);203             int tlcolor = Query_color(1, nid[fy], 'l');204             y = father[fy];205             fy = top[y];206             int trcolor = Query_color(1, nid[y], 'r');207             if (trcolor == tlcolor) ans--;208         }209     }210     //此时x与y已经在一条重链上，而重链上的编号都是连续的211     int rcolor = -1;212     if (x != y)213     {214         215         if (nid[x] < nid[y])216         {217             ans += Query(1, nid[x], nid[y],rcolor);218         }219         else220         {221             ans += Query(1, nid[y], nid[x],rcolor);222         }223     }224     else ans += Query(1, nid[x], nid[y], rcolor);225     return ans;226 }227 228 void Update_path(int x, int y, int nc)229 {
     //将x到y路径上所有结点的值都加上add230     int fx = top[x], fy = top[y];231     while (fx != fy)232     {233         if (dep[fx] >= dep[fy])234         {235             Update(1, nid[fx], nid[x], nc);236             x = father[fx];237             fx = top[x];238         }239         else240         {241             Update(1, nid[fy], nid[y], nc);242             y = father[fy];243             fy = top[y];244         }245     }246     if (x != y)247     {248         if (nid[x] < nid[y]) Update(1, nid[x], nid[y], nc);249         else Update(1, nid[y], nid[x], nc);250     }251     else Update(1, nid[x], nid[y], nc);252 }253 /*-------树链剖分·终-------*/254 255 int main()256 {257     int n, m;258     while (~scanf("%d%d", &n, &m))259     {260         INIT();261         for (int i = 1; i <= n; i++) scanf("%d", &val[i]);262         for (int i = 1; i < n; i++)263         {264             int u, v;265             scanf("%d%d", &u, &v);266             addEdge(u, v);267         }268         dfs1(1,1,1);269         dfs2(1, 1);270         BuildTree(1, 1, n);271         char s[10];272         for (int i = 1; i <= m; i++)273         {274             scanf("%s", s);275             if (s[0] == 'Q')276             {277                 int u, v;278                 scanf("%d%d", &u, &v);279                 printf("%d\n", Query_length(u, v));280             }281             else282             {283                 int u, v, c;284                 scanf("%d%d%d", &u, &v, &c);285                 Update_path(u, v, c);286             }287         }288     }289     return 0;290 }
View Code

3、HYSBZ - 1036 树的统计Count

　　题意：一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：

　　I. CHANGE u t : 把结点u的权值改为t

　　II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

　　III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

　　思路：树链剖分+线段树，点权，单点更新+区间查询。线段树维护区间和和最大值。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 using namespace std;  6 const int maxn = 30000 + 10;  7 const int INF = 0x3f3f3f3f;  8   9 /*-------树链剖分·启-------*/ 10  11 int siz[maxn];//size[i]:以i为根的子树结点个数 12 int top[maxn];//保存结点i所在链的顶端结点 13 int son[maxn];//保存i的重儿子 14 int dep[maxn];//保存结点i的层次（深度） 15 int father[maxn];//保存结点i的父亲结点 16 int nid[maxn];//保存树节点剖分后的对应新编号 17 int oid[maxn];//保存新编号对应在剖分的树中的结点（与nid相反） 18 int cnt = 0;//重编号 19 int val[maxn];//结点值 20 struct EDGE 21 { 22     int from, to, next; 23     EDGE(int ff = 0, int tt = 0, int nn = 0) :from(ff), to(tt), next(nn) {} 24 }edge[maxn * 2]; 25 int Head[maxn], totedge = 0; 26 void addEdge(int from, int to) 27 { 28     edge[totedge] = EDGE(from, to, Head[from]); 29     Head[from] = totedge++; 30     edge[totedge] = EDGE(to, from, Head[to]); 31     Head[to] = totedge++; 32 } 33 void INIT() 34 { 35     memset(Head, -1, sizeof(Head)); 36     totedge = 0; 37  38     memset(son, -1, sizeof(son)); 39     cnt = 0; 40 } 41  42 void dfs1(int u, int fa, int layer) 43 { 44     dep[u] = layer; 45     father[u] = fa; 46     siz[u] = 1; 47     for (int i = Head[u]; i != -1; i = edge[i].next) 48     { 49         int v = edge[i].to; 50         if (v != fa) 51         { 52             dfs1(v, u, layer + 1); 53             siz[u] += siz[v]; 54             if (son[u] == -1 || siz[v] > siz[son[u]]) 55             { 56                 son[u] = v; 57             } 58         } 59     } 60 } 61  62 void dfs2(int u, int Hson) 63 {
     //Hson,重儿子 64     top[u] = Hson; 65     nid[u] = ++cnt; 66     oid[cnt] = u; 67     if (son[u] == -1) return; 68     dfs2(son[u], Hson);//先将当前重链重编号 69     for (int i = Head[u]; i != -1; i = edge[i].next) 70     {
     //对不在重链上的点，自己作为子树的重链起点重编号 71         int v = edge[i].to; 72         if (v != son[u] && v != father[u]) dfs2(v, v); 73     } 74 } 75 /*-------线段树·启————*/ 76 struct treenode 77 { 78     int l, r; 79     long long sum; 80     int max, delay; 81     treenode(int ll = 0, int rr = 0, long long vv = 0, int mx=0,long long tt = 0) :l(ll), r(rr), sum(vv),max(mx), delay(tt) {} 82 }tree[maxn * 4]; 83  84 void PushUp(int root) 85 { 86     tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum; 87     tree[root].max = max(tree[root * 2].max, tree[root * 2 + 1].max); 88 } 89  90 void BuildTree(int root, int l, int r) 91 { 92     tree[root].l = l, tree[root].r = r; 93     tree[root].delay = 0; 94     if (l == r) 95     { 96         tree[root].sum = tree[root].max=val[oid[l]]; 97         return; 98     } 99     int mid = (l + r) / 2;100     BuildTree(root * 2, l, mid);101     BuildTree(root * 2 + 1, mid + 1, r);102     PushUp(root);103 }104 void Pushdown(int root)105 {106     int lson = root * 2, rson = root * 2 + 1;107     if (tree[root].delay)108     {109         tree[lson].sum =1ll* (tree[lson].r - tree[lson].l + 1)*tree[root].delay;110         tree[rson].sum = 1ll*(tree[rson].r - tree[rson].l + 1)*tree[root].delay;111         tree[lson].delay = tree[root].delay;112         tree[rson].delay = tree[root].delay;113         tree[lson].max = tree[rson].max = tree[root].delay;114         tree[root].delay = 0;115     }116 }117 118 void Update(int root, int l, int r, int v)119 {120     if (tree[root].r
           
            r) return;121     if (l <= tree[root].l&&tree[root].r <= r)122     {123         tree[root].delay = v;124         tree[root].max = v;125         tree[root].sum = 1ll*v * (tree[root].r - tree[root].l + 1);126         return;127     }128     Pushdown(root);129     int mid = (tree[root].r + tree[root].l) / 2;130     if (l <= mid)Update(root * 2, l, r, v);131     if (r>mid)Update(root * 2 + 1, l, r, v);132     PushUp(root);133 }134 135 pair
            
              Query(int root, int l, int r)136 {137 if (tree[root].r
             
              r) return make_pair(0,0);138 if (l <= tree[root].l&&tree[root].r <= r)139 {140 return make_pair(tree[root].sum,tree[root].max);141 }142 Pushdown(root);143 int mid = (tree[root].l + tree[root].r) / 2;144 bool flag1 = false, flag2 = false;145 pair
              
               ans,tmp1= pair
               
                (0,0),tmp2= pair
                
                 (0,0);146 if (l <= mid) tmp1 = Query(root * 2, l, r),flag1=true;147 if (r > mid) tmp2 = Query(root * 2 + 1, l, r),flag2=true;148 PushUp(root);149 if (flag1&&flag2) ans.first = tmp1.first + tmp2.first, ans.second = max(tmp1.second, tmp2.second);150 else if (flag1) ans = tmp1;151 else ans = tmp2;152 return ans;153 }154 /*-------线段树·终————*/155 156 pair
                 
                   Query_length(int x, int y)157 { //查询结点x到y路径上所有结点值之和与最大值158 long long sum = 0;159 int maxv = -INF;160 int fx = top[x], fy = top[y];161 pair
                  
                   tmp;162 while (fx != fy)163 {164 if (dep[fx] >= dep[fy])165 {166 tmp= Query(1, nid[fx], nid[x]);//在一条重链上的值用线段树维护、查询167 x = father[fx];168 fx = top[x];169 sum += tmp.first, maxv = max(maxv, tmp.second);170 }171 else172 {173 tmp= Query(1, nid[fy], nid[y]);174 sum += tmp.first, maxv = max(maxv, tmp.second);175 y = father[fy];176 fy = top[y];177 }178 }179 //此时x与y已经在一条重链上，而重链上的编号都是连续的180 if (x != y)181 {182 if (nid[x] < nid[y])183 {184 tmp= Query(1, nid[x], nid[y]);185 sum += tmp.first, maxv = max(maxv, tmp.second);186 }187 else188 {189 tmp= Query(1, nid[y], nid[x]);190 sum += tmp.first, maxv = max(maxv, tmp.second);191 }192 }193 else194 {195 tmp = Query(1, nid[x], nid[y]);196 sum += tmp.first, maxv = max(maxv, tmp.second);197 }198 return make_pair(sum,maxv);199 }200 201 void Update_path(int x, int y, int add)202 { //将x到y路径上所有结点的值都加上add203 int fx = top[x], fy = top[y];204 while (fx != fy)205 {206 if (dep[fx] >= dep[fy])207 {208 Update(1, nid[fx], nid[x], add);209 x = father[fx];210 fx = top[x];211 }212 else213 {214 Update(1, nid[fy], nid[y], add);215 y = father[fy];216 fy = top[y];217 }218 }219 if (x != y)220 {221 if (nid[x] < nid[y]) Update(1, nid[x], nid[y], add);222 else Update(1, nid[y], nid[x], add);223 }224 else Update(1, nid[x], nid[y], add);225 }226 /*-------树链剖分·终-------*/227 228 int main()229 {230 int n,q;231 while (~scanf("%d", &n))232 {233 INIT();234 235 for (int i = 1; i 
                   
                    ans = Query_length(u, v);261 if (s[1] == 'M') printf("%d\n", ans.second);262 else printf("%lld\n", ans.first);263 }264 }265 }266 return 0;267 }
View Code

4、FZU - 2082 过路费

　　题意：有n座城市，由n-1条路相连通，使得任意两座城市之间可达。每条路有过路费，要交过路费才能通过。每条路的过路费经常会更新，现问你，当前情况下，从城市a到城市b最少要花多少过路费。

　　思路：树链剖分+线段树，边权，单点更新+区间查询。注意对边进行编号，以及一些辅助数组记录边指向的结点、边权。

1 #include
       
          2 #include
        
           3 #include
         
            4 using namespace std;  5 const int maxn = 50000 + 10;  6   7 /*-------树链剖分·启-------*/  8   9 int siz[maxn];//size[i]:以i为根的子树结点个数 10 int top[maxn];//保存结点i所在链的顶端结点 11 int son[maxn];//保存i的重儿子 12 int dep[maxn];//保存结点i的层次（深度） 13 int father[maxn];//保存结点i的父亲结点 14 int nid[maxn];//保存树剖分后的指向子结点的边对应的新编号 15 int nval[maxn];//记录所指向的子结点i新编号对应边的边权，用以建立线段树 16 int oid[maxn];//保存新编号对应在剖分的树中的所指向的子结点（与nid相反） 17 int cnt = 0;//重编号 18 int val[maxn];//原树中指向子结点i的边的边权值 19 int linkto[maxn];//记录指向的子结点 20 struct EDGE 21 { 22     int from, to, w, next; 23     EDGE(int ff = 0, int tt = 0, int ww = 0, int nn = 0) :from(ff), to(tt), w(ww), next(nn) {} 24 }edge[maxn * 2]; 25 int Head[maxn], totedge = 0; 26 void addEdge(int from, int to, int w) 27 { 28     edge[totedge] = EDGE(from, to, w, Head[from]); 29     Head[from] = totedge++; 30     edge[totedge] = EDGE(to, from, w, Head[to]); 31     Head[to] = totedge++; 32 } 33 int treeroot = 1; 34 void INIT() 35 { 36     memset(Head, -1, sizeof(Head)); 37     totedge = 0; 38  39     memset(son, -1, sizeof(son)); 40     memset(siz, 0, sizeof(siz)); 41     memset(father, 0, sizeof(father)); 42     memset(top, 0, sizeof(top)); 43     memset(dep, 0, sizeof(dep)); 44     cnt = 0; 45 } 46  47 void dfs1(int u, int fa, int layer) 48 { 49     dep[u] = layer; 50     father[u] = fa; 51     siz[u] = 1; 52     for (int i = Head[u]; i != -1; i = edge[i].next) 53     { 54         int v = edge[i].to; 55         if (v != fa) 56         { 57             dfs1(v, u, layer + 1); 58             siz[u] += siz[v]; 59             linkto[i / 2 + 1] = v; 60             val[v] = edge[i].w; 61             if (son[u] == -1 || siz[v] > siz[son[u]]) 62             { 63                 son[u] = v; 64             } 65         } 66     } 67 } 68  69 void dfs2(int u, int Hson) 70 {
     //Hson,重儿子 71     top[u] = Hson; 72     if (u != treeroot) 73     { 74         nid[u] = ++cnt; 75         oid[cnt] = u; 76         nval[cnt] = val[u]; 77     } 78     if (son[u] == -1) return; 79     dfs2(son[u], Hson);//先将当前重链重编号 80     for (int i = Head[u]; i != -1; i = edge[i].next) 81     {
     //对不在重链上的点，自己作为子树的重链起点重编号 82         int v = edge[i].to; 83         if (v != son[u] && v != father[u]) dfs2(v, v); 84     } 85 } 86 /*-------线段树·启————*/ 87 struct treenode 88 { 89     int l, r; 90     long long v, tmp; 91     treenode(int ll = 0, int rr = 0, long long vv = 0, long long tt = 0) :l(ll), r(rr), v(vv), tmp(tt) {} 92 }tree[maxn * 4]; 93  94 void BuildTree(int root, int l, int r) 95 { 96     tree[root].l = l, tree[root].r = r; 97     tree[root].tmp = 0; 98     if (l == r) 99     {100         tree[root].v = nval[l];101         return;102     }103     int mid = (l + r) / 2;104     BuildTree(root * 2, l, mid);105     BuildTree(root * 2 + 1, mid + 1, r);106     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;107 }108 void Pushdown(int root)109 {110     int lson = root * 2, rson = root * 2 + 1;111     if (tree[root].tmp)112     {113         tree[lson].v = (tree[lson].r - tree[lson].l + 1)*tree[root].tmp;114         tree[rson].v = (tree[rson].r - tree[rson].l + 1)*tree[root].tmp;115         tree[lson].tmp = tree[root].tmp;116         tree[rson].tmp = tree[root].tmp;117         tree[root].tmp = 0;118     }119 }120 void PushUp(int root)121 {122     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;123 }124 void Update(int root, int l, int r, int add)125 {126     if (tree[root].r
          
           r) return;127     if (l <= tree[root].l&&tree[root].r <= r)128     {129         tree[root].tmp = add;130         tree[root].v = add * (tree[root].r - tree[root].l + 1);131         return;132     }133     Pushdown(root);134     int mid = (tree[root].r + tree[root].l) / 2;135     if (l <= mid)Update(root * 2, l, r, add);136     if (r>mid)Update(root * 2 + 1, l, r, add);137     PushUp(root);138 }139 140 long long Query(int root, int l, int r)141 {142     if (tree[root].r
           
            r) return 0;143     if (l <= tree[root].l&&tree[root].r <= r)144     {145         return tree[root].v;146     }147     Pushdown(root);148     long long tsum = Query(root * 2, l, r) + Query(root * 2 + 1, l, r);149     PushUp(root);150     return tsum;151 }152 /*-------线段树·终————*/153 154 long long Query_length(int x, int y)155 {
     //查询x到y路径上边权和156     int fx = top[x], fy = top[y];157     long long ans = 0;158     while (fx != fy)159     {160         if (dep[fx] > dep[fy])161         {162             int id1 = nid[fx], id2 = nid[x];163             ans += Query(1, id1, id2);164             x = father[fx];165             fx = top[x];166         }167         else168         {169             int id1 = nid[fy], id2 = nid[y];170             ans += Query(1, id1, id2);171             y = father[fy];172             fy = top[y];173         }174     }175     if (x != y)176     {177         if (dep[x] > dep[y])178         {179             int id1 = nid[son[y]], id2 = nid[x];180             ans += Query(1, id1, id2);181         }182         else183         {184             int id1 = nid[son[x]], id2 = nid[y];185             ans += Query(1, id1, id2);186         }187     }188     return ans;189 }190 void Update_path(int x, int y, int add)191 {
     //将x到y路径上所有边的值都加上或修改为add192     int fx = top[x], fy = top[y];193     while (fx != fy)194     {195         if (dep[fx] >= dep[fy])196         {197             Update(1, nid[fx], nid[x], add);198             x = father[fx];199             fx = top[x];200         }201         else202         {203             Update(1, nid[fy], nid[y], add);204             y = father[fy];205             fy = top[y];206         }207     }208     if (x != y)209     {210         if (dep[x] < dep[y]) Update(1, nid[son[x]], nid[y], add);211         else Update(1, nid[son[y]], nid[x], add);212     }213 }214 /*-------树链剖分·终-------*/215 216 int main()217 {218     int n, m;219     while (~scanf("%d%d", &n, &m))220     {221         INIT();222         for (int i = 1; i < n; i++)223         {224             int u, v, w;225             scanf("%d%d%d", &u, &v, &w);226             addEdge(u, v, w);227         }228         dfs1(1, 1, 1);229         dfs2(1, 1);230         BuildTree(1, 1, cnt);231         for (int i = 1; i <= m; i++)232         {233             int flag;234             scanf("%d", &flag);235             if (flag == 1)236             {237                 int u,v;238                 scanf("%d%d", &u,&v);239                 long long ans = Query_length(u,v);240                 printf("%lld\n", ans);241             }242             else243             {244                 int id, v;245                 scanf("%d%d", &id, &v);246                 int nID = nid[linkto[id]];247                 Update(1, nID, nID, v);248             }249 250         }251 252     }253     return 0;254 }
View Code

 5、LightOJ - 1348 Aladdin and the Return Journey

　　题意：有一棵树，每次更新一个点的权值或者查询u到v路径上所有结点权值之和。

　　思路：树链剖分+线段树，点权，单点更新和区间查询。

1 #include
       
          2 #include
        
           3 #include
         
            4 using namespace std;  5 const int maxn = 30000 + 10;  6   7 /*-------树链剖分·启-------*/  8   9 int siz[maxn];//size[i]:以i为根的子树结点个数 10 int top[maxn];//保存结点i所在链的顶端结点 11 int son[maxn];//保存i的重儿子 12 int dep[maxn];//保存结点i的层次（深度） 13 int father[maxn];//保存结点i的父亲结点 14 int nid[maxn];//保存树节点剖分后的对应新编号 15 int oid[maxn];//保存新编号对应在剖分的树中的结点（与nid相反） 16 int cnt = 0;//重编号 17 int val[maxn];//结点值 18 struct EDGE 19 { 20     int from, to, next; 21     EDGE(int ff = 0, int tt = 0, int nn = 0) :from(ff), to(tt), next(nn) {} 22 }edge[maxn * 2]; 23 int Head[maxn], totedge = 0; 24 void addEdge(int from, int to) 25 { 26     edge[totedge] = EDGE(from, to, Head[from]); 27     Head[from] = totedge++; 28     edge[totedge] = EDGE(to, from, Head[to]); 29     Head[to] = totedge++; 30 } 31 void INIT() 32 { 33     memset(Head, -1, sizeof(Head)); 34     totedge = 0; 35  36     memset(son, -1, sizeof(son)); 37     memset(siz, 0, sizeof(siz)); 38     memset(father, 0, sizeof(father)); 39     memset(top, 0, sizeof(top)); 40     memset(dep, 0, sizeof(dep)); 41     cnt = 0; 42 } 43  44 void dfs1(int u, int fa, int layer) 45 { 46     dep[u] = layer; 47     father[u] = fa; 48     siz[u] = 1; 49     for (int i = Head[u]; i != -1; i = edge[i].next) 50     { 51         int v = edge[i].to; 52         if (v != fa) 53         { 54             dfs1(v, u, layer + 1); 55             siz[u] += siz[v]; 56             if (son[u] == -1 || siz[v] > siz[son[u]]) 57             { 58                 son[u] = v; 59             } 60         } 61     } 62 } 63  64 void dfs2(int u, int Hson) 65 {
     //Hson,重儿子 66     top[u] = Hson; 67     nid[u] = ++cnt; 68     oid[cnt] = u; 69     if (son[u] == -1) return; 70     dfs2(son[u], Hson);//先将当前重链重编号 71     for (int i = Head[u]; i != -1; i = edge[i].next) 72     {
     //对不在重链上的点，自己作为子树的重链起点重编号 73         int v = edge[i].to; 74         if (v != son[u] && v != father[u]) dfs2(v, v); 75     } 76 } 77 /*-------线段树·启————*/ 78 struct treenode 79 { 80     int l, r; 81     long long v, delay; 82     treenode(int ll = 0, int rr = 0, long long vv = 0, long long tt = 0) :l(ll), r(rr), v(vv), delay(tt) {} 83 }tree[maxn * 4]; 84  85 void PushUp(int root) 86 { 87     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v; 88 } 89 void BuildTree(int root, int l, int r) 90 { 91     tree[root].l = l, tree[root].r = r; 92     tree[root].delay = 0; 93     if (l == r) 94     { 95         tree[root].v = val[oid[l]]; 96         return; 97     } 98     int mid = (l + r) / 2; 99     BuildTree(root * 2, l, mid);100     BuildTree(root * 2 + 1, mid + 1, r);101     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;102 }103 void Pushdown(int root)104 {105     int lson = root * 2, rson = root * 2 + 1;106     if (tree[root].delay)107     {108         tree[lson].v = (tree[lson].r - tree[lson].l + 1)*tree[root].delay;109         tree[rson].v = (tree[rson].r - tree[rson].l + 1)*tree[root].delay;110         tree[lson].delay = tree[root].delay;111         tree[rson].delay = tree[root].delay;112         tree[root].delay = 0;113     }114 }115 116 void Update(int root, int l, int r, int add)117 {118     if (tree[root].r
          
           r) return;119     if (l <= tree[root].l&&tree[root].r <= r)120     {121         tree[root].delay = add;122         tree[root].v = add * (tree[root].r - tree[root].l + 1);123         return;124     }125     Pushdown(root);126     int mid = (tree[root].r + tree[root].l) / 2;127     if (l <= mid)Update(root * 2, l, r, add);128     if (r>mid)Update(root * 2 + 1, l, r, add);129     PushUp(root);130 }131 132 long long Query(int root, int l, int r)133 {134     if (tree[root].r
           
            r) return 0;135     if (l <= tree[root].l&&tree[root].r <= r)136     {137         return tree[root].v;138     }139     Pushdown(root);140     long long tsum = Query(root * 2, l, r) + Query(root * 2 + 1, l, r);141     PushUp(root);142     return tsum;143 }144 /*-------线段树·终————*/145 146 long long Query_length(int x, int y)147 {
     //查询结点x到y路径上所有结点值之和148     long long ans = 0;149     int fx = top[x], fy = top[y];150     while (fx != fy)151     {152         if (dep[fx] >= dep[fy])153         {154             ans += Query(1, nid[fx], nid[x]);//在一条重链上的值用线段树维护、查询155             x = father[fx];156             fx = top[x];157         }158         else159         {160             ans += Query(1, nid[fy], nid[y]);161             y = father[fy];162             fy = top[y];163         }164     }165     //此时x与y已经在一条重链上，而重链上的编号都是连续的166     if (x != y)167     {168         if (nid[x] < nid[y])169         {170             ans += Query(1, nid[x], nid[y]);171         }172         else173         {174             ans += Query(1, nid[y], nid[x]);175         }176     }177     else ans += Query(1, nid[x], nid[y]);178     return ans;179 }180 181 void Update_path(int x, int y, int add)182 {
     //将x到y路径上所有结点的值都加上add183     int fx = top[x], fy = top[y];184     while (fx != fy)185     {186         if (dep[fx] >= dep[fy])187         {188             Update(1, nid[fx], nid[x], add);189             x = father[fx];190             fx = top[x];191         }192         else193         {194             Update(1, nid[fy], nid[y], add);195             y = father[fy];196             fy = top[y];197         }198     }199     if (x != y)200     {201         if (nid[x] < nid[y]) Update(1, nid[x], nid[y], add);202         else Update(1, nid[y], nid[x], add);203     }204     else Update(1, nid[x], nid[y], add);205 }206 /*-------树链剖分·终-------*/207 208 int main()209 {210     int t,n,q;211     int Case = 1;212     scanf("%d", &t);213     while (t--)214     {215         printf("Case %d:\n", Case++);216         scanf("%d", &n);217         INIT();218         for (int i = 1; i <= n; i++) scanf("%d", &val[i]);219         for (int i = 1; i
View Code

 6、Housewife Wind POJ - 2763

　　题意：有一个小镇，有n户人家和n-1条路（树），有一位母亲要去接孩子，起点位于s。两种操作：修改通过某一条路的时间；母亲要从当前位置到达u的位置接孩子，求时间。

　　思路：树链剖分+线段树，边权，区间查询+单点更新。

1 #include
       
          2 #include
        
           3 using namespace std;  4 const int maxn = 100000+10;  5   6 /*-------树链剖分·启-------*/  7   8 int siz[maxn];//size[i]:以i为根的子树结点个数  9 int top[maxn];//保存结点i所在链的顶端结点 10 int son[maxn];//保存i的重儿子 11 int dep[maxn];//保存结点i的层次（深度） 12 int father[maxn];//保存结点i的父亲结点 13 int nid[maxn];//保存树剖分后的指向子结点的边对应的新编号 14 int nval[maxn];//记录所指向的子结点i新编号对应边的边权，用以建立线段树 15 int oid[maxn];//保存新编号对应在剖分的树中的所指向的子结点（与nid相反） 16 int cnt = 0;//重编号 17 int val[maxn];//原树中指向子结点i的边的边权值 18 int linkto[maxn];//记录指向的子结点 19 struct EDGE 20 { 21     int from, to,w, next; 22     EDGE(int ff = 0, int tt = 0,int ww=0, int nn = 0) :from(ff), to(tt),w(ww), next(nn) {} 23 }edge[maxn * 2]; 24 int Head[maxn], totedge = 0; 25 void addEdge(int from, int to,int w) 26 { 27     edge[totedge] = EDGE(from, to, w,Head[from]); 28     Head[from] = totedge++; 29     edge[totedge] = EDGE(to, from,w, Head[to]); 30     Head[to] = totedge++; 31 } 32 int treeroot = 1; 33 void INIT() 34 { 35     memset(Head, -1, sizeof(Head)); 36     totedge = 0; 37  38     memset(son, -1, sizeof(son)); 39     memset(siz, 0, sizeof(siz)); 40     memset(father, 0, sizeof(father)); 41     memset(top, 0, sizeof(top)); 42     memset(dep, 0, sizeof(dep)); 43     cnt = 0; 44 } 45  46 void dfs1(int u, int fa, int layer) 47 { 48     dep[u] = layer; 49     father[u] = fa; 50     siz[u] = 1; 51     for (int i = Head[u]; i != -1; i = edge[i].next) 52     { 53         int v = edge[i].to; 54         if (v != fa) 55         { 56             dfs1(v, u, layer + 1); 57             siz[u] += siz[v]; 58             linkto[i / 2 + 1] = v; 59             val[v] = edge[i].w; 60             if (son[u] == -1 || siz[v] > siz[son[u]]) 61             { 62                 son[u] = v; 63             } 64         } 65     } 66 } 67  68 void dfs2(int u, int Hson) 69 {
     //Hson,重儿子 70     top[u] = Hson; 71     if (u != treeroot) 72     { 73         nid[u] = ++cnt; 74         oid[cnt] = u; 75         nval[cnt] = val[u]; 76     } 77     if (son[u] == -1) return; 78     dfs2(son[u], Hson);//先将当前重链重编号 79     for (int i = Head[u]; i != -1; i = edge[i].next) 80     {
     //对不在重链上的点，自己作为子树的重链起点重编号 81         int v = edge[i].to; 82         if (v != son[u] && v != father[u]) dfs2(v, v); 83     } 84 } 85 /*-------线段树·启————*/ 86 struct treenode 87 { 88     int l, r; 89     long long v, tmp; 90     treenode(int ll = 0, int rr = 0, long long vv = 0, long long tt = 0) :l(ll), r(rr), v(vv), tmp(tt) {} 91 }tree[maxn * 4]; 92  93 void BuildTree(int root, int l, int r) 94 { 95     tree[root].l = l, tree[root].r = r; 96     tree[root].tmp = 0; 97     if (l == r) 98     { 99         tree[root].v = nval[l];100         return;101     }102     int mid = (l + r) / 2;103     BuildTree(root * 2, l, mid);104     BuildTree(root * 2 + 1, mid + 1, r);105     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;106 }107 void Pushdown(int root)108 {109     int lson = root * 2, rson = root * 2 + 1;110     if (tree[root].tmp)111     {112         tree[lson].v = (tree[lson].r - tree[lson].l + 1)*tree[root].tmp;113         tree[rson].v = (tree[rson].r - tree[rson].l + 1)*tree[root].tmp;114         tree[lson].tmp = tree[root].tmp;115         tree[rson].tmp = tree[root].tmp;116         tree[root].tmp = 0;117     }118 }119 void PushUp(int root)120 {121     tree[root].v = tree[root * 2].v + tree[root * 2 + 1].v;122 }123 void Update(int root, int l, int r, int add)124 {125     if (tree[root].r
         
          r) return;126     if (l <= tree[root].l&&tree[root].r <= r)127     {128         tree[root].tmp = add;129         tree[root].v = add*(tree[root].r-tree[root].l+1);130         return;131     }132     Pushdown(root);133     int mid = (tree[root].r + tree[root].l) / 2;134     if (l <= mid)Update(root * 2, l, r, add);135     if (r>mid)Update(root * 2 + 1, l, r, add);136     PushUp(root);137 }138 139 long long Query(int root, int l, int r)140 {141     if (tree[root].r
          
           r) return 0;142     if (l <= tree[root].l&&tree[root].r <= r)143     {144         return tree[root].v;145     }146     Pushdown(root);147     long long tsum = Query(root * 2, l, r) + Query(root * 2 + 1, l, r);148     PushUp(root);149     return tsum;150 }151 /*-------线段树·终————*/152 153 long long Query_length(int x, int y)154 {
     //查询x到y路径上边权和155     int fx = top[x], fy = top[y];156     long long ans = 0;157     while (fx != fy)158     {159         if (dep[fx] > dep[fy])160         {161             int id1 = nid[fx],id2=nid[x];162             ans += Query(1, id1, id2);163             x = father[fx];164             fx = top[x];165         }166         else167         {168             int id1 = nid[fy], id2 = nid[y];169             ans += Query(1, id1, id2);170             y = father[fy];171             fy = top[y];172         }173     }174     if (x != y)175     {176         if (dep[x] > dep[y])177         {178             int id1 = nid[son[y]], id2 = nid[x];179             ans += Query(1, id1, id2);180         }181         else182         {183             int id1 = nid[son[x]], id2 = nid[y];184             ans += Query(1, id1, id2);185         }186     }187     return ans;188 }189 void Update_path(int x, int y, int add)190 {
     //将x到y路径上所有边的值都加上或修改为add191     int fx = top[x], fy = top[y];192     while (fx != fy)193     {194         if (dep[fx] >= dep[fy])195         {196             Update(1, nid[fx], nid[x], add);197             x = father[fx];198             fx = top[x];199         }200         else201         {202             Update(1, nid[fy], nid[y], add);203             y = father[fy];204             fy = top[y];205         }206     }207     if (x != y)208     {209         if (dep[x] < dep[y]) Update(1, nid[son[x]], nid[y], add);210         else Update(1, nid[son[y]], nid[x], add);211     }212 }213 /*-------树链剖分·终-------*/214 215 int main()216 {217     int n, q, s;218     while (~scanf("%d%d%d", &n, &q, &s))219     {220         INIT();221         for (int i = 1; i < n; i++)222         {223             int u, v, w;224             scanf("%d%d%d", &u, &v, &w);225             addEdge(u, v, w);226         }227         dfs1(1,1,1);228         dfs2(1,1);229         BuildTree(1, 1, cnt);230         for (int i = 1; i <= q; i++)231         {232             int flag;233             scanf("%d", &flag);234             if (flag == 0)235             {236                 int des;237                 scanf("%d", &des);238                 long long ans = Query_length(s, des);239                 s = des;240                 printf("%lld\n", ans);241             }242             else243             {244                 int id, v;245                 scanf("%d%d", &id, &v);246                 int nID = nid[linkto[id]];247                 Update(1, nID, nID, v);248             }249 250         }251 252     }253     return 0;254 }
View Code

7、Query on a tree SPOJ - QTREE

 　　题意：有一棵树，每次将一条边的权值修改或者询问u到v路径上的最大边权。

　　思路：树链剖分+线段树，边权，区间查询+单点更新。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 using namespace std;  6 const int maxn = 10000 + 10;  7   8 /*-------树链剖分·启-------*/  9  10 int siz[maxn];//size[i]:以i为根的子树结点个数 11 int top[maxn];//保存结点i所在链的顶端结点 12 int son[maxn];//保存i的重儿子 13 int dep[maxn];//保存结点i的层次（深度） 14 int father[maxn];//保存结点i的父亲结点 15 int nid[maxn];//保存树剖分后的指向子结点的边对应的新编号 16 int nval[maxn];//记录所指向的子结点i新编号对应边的边权，用以建立线段树 17 int oid[maxn];//保存新编号对应在剖分的树中的所指向的子结点（与nid相反） 18 int cnt = 0;//重编号 19 int val[maxn];//原树中指向子结点i的边的边权值 20 int linkto[maxn];//记录指向的子结点 21 struct EDGE 22 { 23     int from, to, w, next; 24     EDGE(int ff = 0, int tt = 0, int ww = 0, int nn = 0) :from(ff), to(tt), w(ww), next(nn) {} 25 }edge[maxn * 2]; 26 int Head[maxn], totedge = 0; 27 void addEdge(int from, int to, int w) 28 { 29     edge[totedge] = EDGE(from, to, w, Head[from]); 30     Head[from] = totedge++; 31     edge[totedge] = EDGE(to, from, w, Head[to]); 32     Head[to] = totedge++; 33 } 34 int treeroot = 1; 35 void INIT() 36 { 37     memset(Head, -1, sizeof(Head)); 38     totedge = 0; 39  40     memset(son, -1, sizeof(son)); 41     memset(siz, 0, sizeof(siz)); 42     memset(father, 0, sizeof(father)); 43     memset(top, 0, sizeof(top)); 44     memset(dep, 0, sizeof(dep)); 45     cnt = 0; 46 } 47  48 void dfs1(int u, int fa, int layer) 49 { 50     dep[u] = layer; 51     father[u] = fa; 52     siz[u] = 1; 53     for (int i = Head[u]; i != -1; i = edge[i].next) 54     { 55         int v = edge[i].to; 56         if (v != fa) 57         { 58             dfs1(v, u, layer + 1); 59             siz[u] += siz[v]; 60             linkto[i / 2 + 1] = v; 61             val[v] = edge[i].w; 62             if (son[u] == -1 || siz[v] > siz[son[u]]) 63             { 64                 son[u] = v; 65             } 66         } 67     } 68 } 69  70 void dfs2(int u, int Hson) 71 {
     //Hson,重儿子 72     top[u] = Hson; 73     if (u != treeroot) 74     { 75         nid[u] = ++cnt; 76         oid[cnt] = u; 77         nval[cnt] = val[u]; 78     } 79     if (son[u] == -1) return; 80     dfs2(son[u], Hson);//先将当前重链重编号 81     for (int i = Head[u]; i != -1; i = edge[i].next) 82     {
     //对不在重链上的点，自己作为子树的重链起点重编号 83         int v = edge[i].to; 84         if (v != son[u] && v != father[u]) dfs2(v, v); 85     } 86 } 87 /*-------线段树·启————*/ 88 struct treenode 89 { 90     int l, r; 91     long long v, tmp; 92     treenode(int ll = 0, int rr = 0, long long vv = 0, long long tt = 0) :l(ll), r(rr), v(vv), tmp(tt) {} 93 }tree[maxn * 4]; 94  95 void PushUp(int root) 96 { 97     tree[root].v = max(tree[root * 2].v, tree[root * 2 + 1].v); 98 } 99 100 void BuildTree(int root, int l, int r)101 {102     tree[root].l = l, tree[root].r = r;103     tree[root].tmp = 0;104     if (l == r)105     {106         tree[root].v = nval[l];107         return;108     }109     int mid = (l + r) / 2;110     BuildTree(root * 2, l, mid);111     BuildTree(root * 2 + 1, mid + 1, r);112     tree[root].v = max(tree[root * 2].v, tree[root * 2 + 1].v);113 }114 void PushDown(int root)115 {116     int lson = root * 2, rson = root * 2 + 1;117     if (tree[root].tmp)118     {119         tree[lson].v = (tree[lson].r - tree[lson].l + 1)*tree[root].tmp;120         tree[rson].v = (tree[rson].r - tree[rson].l + 1)*tree[root].tmp;121         tree[lson].tmp = tree[root].tmp;122         tree[rson].tmp = tree[root].tmp;123         tree[root].tmp = 0;124     }125 }126 127 void Update(int root, int l, int r, int add)128 {129     if (tree[root].r
           
            r) return;130     if (l <= tree[root].l&&tree[root].r <= r)131     {132         tree[root].tmp = add;133         tree[root].v = add * (tree[root].r - tree[root].l + 1);134         return;135     }136     PushDown(root);137     int mid = (tree[root].r + tree[root].l) / 2;138     if (l <= mid)Update(root * 2, l, r, add);139     if (r>mid)Update(root * 2 + 1, l, r, add);140     PushUp(root);141 }142 143 long long Query(int root, int l, int r)144 {145     if (tree[root].r
            
             r) return 0;146 if (l <= tree[root].l&&tree[root].r <= r)147 {148 return tree[root].v;149 }150 PushDown(root);151 long long ans = 0, tmp1, tmp2;152 bool flag = false;153 int mid = (tree[root].l + tree[root].r) / 2;154 if (l <= mid) tmp1 = Query(root * 2, l, r), flag = true;155 if (r > mid) tmp2 = Query(root * 2 + 1, l, r);156 PushUp(root);157 if (flag) ans = max(tmp1, tmp2);158 else ans = tmp2;159 return ans;160 }161 /*-------线段树·终————*/162 163 long long Query_length(int x, int y)164 { //查询x到y路径上最大边权165 int fx = top[x], fy = top[y];166 long long ans = 0;167 bool flag = false;168 while (fx != fy)169 {170 if (dep[fx] > dep[fy])171 {172 173 int id1 = nid[fx], id2 = nid[x];174 long long tmp = Query(1, id1, id2);175 x = father[fx];176 fx = top[x];177 if (!flag) ans = tmp;178 else ans = max(ans, tmp);179 flag = true;180 }181 else182 {183 int id1 = nid[fy], id2 = nid[y];184 long long tmp = Query(1, id1, id2);185 y = father[fy];186 fy = top[y];187 if (!flag) ans = tmp;188 else ans = max(ans, tmp);189 flag = true;190 }191 }192 if (x != y)193 {194 if (dep[x] > dep[y])195 {196 197 int id1 = nid[son[y]], id2 = nid[x];198 long long tmp = Query(1, id1, id2);199 if (!flag) ans = tmp;200 else ans = max(ans, tmp);201 flag = true;202 }203 else204 {205 int id1 = nid[son[x]], id2 = nid[y];206 long long tmp = Query(1, id1, id2);207 if (!flag) ans = tmp;208 else ans = max(ans, tmp);209 flag = true;210 }211 }212 return ans;213 }214 void Update_path(int x, int y, int add)215 { //将x到y路径上所有边的值都加上或修改为add216 int fx = top[x], fy = top[y];217 while (fx != fy)218 {219 if (dep[fx] >= dep[fy])220 {221 Update(1, nid[fx], nid[x], add);222 x = father[fx];223 fx = top[x];224 }225 else226 {227 Update(1, nid[fy], nid[y], add);228 y = father[fy];229 fy = top[y];230 }231 }232 if (x != y)233 {234 if (dep[x] < dep[y]) Update(1, nid[son[x]], nid[y], add);235 else Update(1, nid[son[y]], nid[x], add);236 }237 }238 /*-------树链剖分·终-------*/239 240 int main()241 {242 int t;243 scanf("%d", &t);244 int n, m;245 while (t--)246 {247 INIT();248 scanf("%d", &n);249 for (int i = 1; i < n; i++)250 {251 int u, v, w;252 scanf("%d%d%d", &u, &v, &w);253 addEdge(u, v, w);254 }255 dfs1(1, 1, 1);256 dfs2(1, 1);257 BuildTree(1, 1, cnt);258 char s[10];259 while (true)260 {261 scanf("%s", s);262 if (s[0] == 'Q')263 {264 int u, v;265 scanf("%d%d", &u, &v);266 long long ans = Query_length(u, v);267 printf("%lld\n", ans);268 }269 else if (s[0] == 'C')270 {271 int id, v;272 scanf("%d%d", &id, &v);273 int nID = nid[linkto[id]];274 Update(1, nID, nID, v);275 }276 else277 {278 break;279 }280 }281 }282 return 0;283 }
View Code

 8、POJ - 3237 Tree 

　　题意：有一棵树，每次改变一条边的边权，或将一条路径上所有边权取反，或者求一条路径上边权的最大值。

　　思路：树链剖分+线段树，边权。主要练习取反。记录一个错误：建树时忘记向上更新最小值，只更新了最大值，调了好久没发现。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 using namespace std;  6 const int maxn = 10000+ 10;  7   8 /*-------树链剖分·启-------*/  9  10 int siz[maxn];//size[i]:以i为根的子树结点个数 11 int top[maxn];//保存结点i所在链的顶端结点 12 int son[maxn];//保存i的重儿子 13 int dep[maxn];//保存结点i的层次（深度） 14 int father[maxn];//保存结点i的父亲结点 15 int nid[maxn];//保存树剖分后的指向子结点的边对应的新编号 16 int nval[maxn];//记录所指向的子结点i新编号对应边的边权，用以建立线段树 17 int oid[maxn];//保存新编号对应在剖分的树中的所指向的子结点（与nid相反） 18 int cnt = 0;//重编号 19 int val[maxn];//原树中指向子结点i的边的边权值 20 int linkto[maxn];//记录指向的子结点 21 struct EDGE 22 { 23     int from, to, w, next; 24     EDGE(int ff = 0, int tt = 0, int ww = 0, int nn = 0) :from(ff), to(tt), w(ww), next(nn) {} 25 }edge[maxn * 2]; 26 int Head[maxn], totedge = 0; 27 void addEdge(int from, int to, int w) 28 { 29     edge[totedge] = EDGE(from, to, w, Head[from]); 30     Head[from] = totedge++; 31     edge[totedge] = EDGE(to, from, w, Head[to]); 32     Head[to] = totedge++; 33 } 34 int treeroot = 1; 35 void INIT() 36 { 37     memset(Head, -1, sizeof(Head)); 38     totedge = 0; 39  40     memset(son, -1, sizeof(son)); 41     cnt = 0; 42 } 43  44 void dfs1(int u, int fa, int layer) 45 { 46     dep[u] = layer; 47     father[u] = fa; 48     siz[u] = 1; 49     for (int i = Head[u]; i != -1; i = edge[i].next) 50     { 51         int v = edge[i].to; 52         if (v != fa) 53         { 54             dfs1(v, u, layer + 1); 55             siz[u] += siz[v]; 56             linkto[i / 2 + 1] = v; 57             val[v] = edge[i].w; 58             if (son[u] == -1 || siz[v] > siz[son[u]]) 59             { 60                 son[u] = v; 61             } 62         } 63     } 64 } 65  66 void dfs2(int u, int Hson) 67 {
     //Hson,重儿子 68     top[u] = Hson; 69     if (u != treeroot) 70     { 71         nid[u] = ++cnt; 72         oid[cnt] = u; 73         nval[cnt] = val[u]; 74     } 75     if (son[u] == -1) return; 76     dfs2(son[u], Hson);//先将当前重链重编号 77     for (int i = Head[u]; i != -1; i = edge[i].next) 78     {
     //对不在重链上的点，自己作为子树的重链起点重编号 79         int v = edge[i].to; 80         if (v != son[u] && v != father[u]) dfs2(v, v); 81     } 82 } 83 /*-------线段树·启————*/ 84 struct treenode 85 { 86     int l, r; 87     long long maxv, minv; 88     int delay; 89     treenode(int ll = 0, int rr = 0, long long vv = 0, long long mv = 0, int tt = 0) :l(ll), r(rr), maxv(vv), minv(mv), delay(tt) {} 90 }tree[maxn * 4]; 91  92 void PushUp(int root) 93 { 94     tree[root].maxv = max(tree[root * 2].maxv, tree[root * 2 + 1].maxv); 95     tree[root].minv = min(tree[root * 2].minv, tree[root * 2 + 1].minv); 96 } 97  98 void BuildTree(int root, int l, int r) 99 {100     tree[root].l = l, tree[root].r = r;101     tree[root].delay = 0;102     if (l == r)103     {104         tree[root].maxv = tree[root].minv = nval[l];105         return;106     }107     int mid = (l + r) / 2;108     BuildTree(root * 2, l, mid);109     BuildTree(root * 2 + 1, mid + 1, r);110     PushUp(root);111 }112 void PushDown(int root)113 {114     int lson = root * 2, rson = root * 2 + 1;115     if (tree[root].delay)116     {117         swap(tree[lson].maxv, tree[lson].minv);118         tree[lson].maxv = -tree[lson].maxv, tree[lson].minv = -tree[lson].minv;119         swap(tree[rson].maxv, tree[rson].minv);120         tree[rson].maxv = -tree[rson].maxv, tree[rson].minv = -tree[rson].minv;121         tree[lson].delay ^= 1;122         tree[rson].delay ^= 1;123         tree[root].delay = 0;124     }125 }126 127 void Update(int root, int l, int r, int v)128 {
     //单点修改129     if (tree[root].r
           
            r) return;130     if (tree[root].l == tree[root].r)131     {132         tree[root].maxv = tree[root].minv = v;133         tree[root].delay = 0;134         return;135     }136     PushDown(root);137     int mid = (tree[root].r + tree[root].l) / 2;138     if (l <= mid)Update(root * 2, l, r, v);139     if (r > mid)Update(root * 2 + 1, l, r, v);140     PushUp(root);141 }142 void Update_Neg(int root, int l, int r)143 {
     //取反144     if (tree[root].r
            
             r) return;145 if (l <= tree[root].l&&tree[root].r <= r)146 {147 tree[root].delay ^= 1;148 swap(tree[root].maxv, tree[root].minv);149 tree[root].maxv = -tree[root].maxv, tree[root].minv = -tree[root].minv;150 return;151 }152 PushDown(root);153 int mid = (tree[root].r + tree[root].l) / 2;154 if (l <= mid)Update_Neg(root * 2, l, r);155 if (r > mid)Update_Neg(root * 2 + 1, l, r);156 PushUp(root);157 }158 159 long long Query(int root, int l, int r)160 {161 if (tree[root].r
             
              r) return 0;162 if (l <= tree[root].l&&tree[root].r <= r)163 {164 return tree[root].maxv;165 }166 PushDown(root);167 long long ans = 0, tmp1, tmp2;168 bool flag1 = false, flag2 = false;169 int mid = (tree[root].l + tree[root].r) / 2;170 if (l <= mid) tmp1 = Query(root * 2, l, r), flag1 = true;171 if (r > mid) tmp2 = Query(root * 2 + 1, l, r), flag2 = true;172 PushUp(root);173 if (flag1&&flag2) ans = max(tmp1, tmp2);174 else if (flag2)ans = tmp2;175 else ans = tmp1;176 return ans;177 }178 /*-------线段树·终————*/179 180 long long Query_length(int x, int y)181 { //查询x到y路径上最大边权182 int fx = top[x], fy = top[y];183 long long ans = 0;184 bool flag = false;185 while (fx != fy)186 {187 if (dep[fx] > dep[fy])188 {189 190 int id1 = nid[fx], id2 = nid[x];191 long long tmp = Query(1, id1, id2);192 x = father[fx];193 fx = top[x];194 if (!flag) ans = tmp;195 else ans = max(ans, tmp);196 flag = true;197 }198 else199 {200 int id1 = nid[fy], id2 = nid[y];201 long long tmp = Query(1, id1, id2);202 y = father[fy];203 fy = top[y];204 if (!flag) ans = tmp;205 else ans = max(ans, tmp);206 flag = true;207 }208 }209 if (x != y)210 {211 if (dep[x] > dep[y])212 {213 214 int id1 = nid[son[y]], id2 = nid[x];215 long long tmp = Query(1, id1, id2);216 if (!flag) ans = tmp;217 else ans = max(ans, tmp);218 flag = true;219 }220 else221 {222 int id1 = nid[son[x]], id2 = nid[y];223 long long tmp = Query(1, id1, id2);224 if (!flag) ans = tmp;225 else ans = max(ans, tmp);226 flag = true;227 }228 }229 return ans;230 }231 void Update_path(int x, int y)232 { //将x到y路径上所有边的值都取反233 int fx = top[x], fy = top[y];234 while (fx != fy)235 {236 if (dep[fx] >= dep[fy])237 {238 Update_Neg(1, nid[fx], nid[x]);239 x = father[fx];240 fx = top[x];241 }242 else243 {244 Update_Neg(1, nid[fy], nid[y]);245 y = father[fy];246 fy = top[y];247 }248 }249 if (x != y)250 {251 if (dep[x] < dep[y]) Update_Neg(1, nid[son[x]], nid[y]);252 else Update_Neg(1, nid[son[y]], nid[x]);253 }254 }255 /*-------树链剖分·终-------*/256 257 int main()258 {259 int t;260 scanf("%d", &t);261 int n, m;262 while (t--)263 {264 INIT();265 scanf("%d", &n);266 for (int i = 1; i < n; i++)267 {268 int u, v, w;269 scanf("%d%d%d", &u, &v, &w);270 addEdge(u, v, w);271 }272 dfs1(1, 1, 1);273 dfs2(1, 1);274 BuildTree(1, 1, cnt);275 char s[10];276 while (true)277 {278 scanf("%s", s);279 if (s[0] == 'Q')280 {281 int u, v;282 scanf("%d%d", &u, &v);283 long long ans = Query_length(u, v);284 printf("%lld\n", ans);285 }286 else if (s[0] == 'C')287 {288 int id, v;289 scanf("%d%d", &id, &v);290 int nID = nid[linkto[id]];291 Update(1, nID, nID, v);292 }293 else if (s[0] == 'N')294 {295 int u, v;296 scanf("%d%d", &u, &v);297 Update_path(u, v);298 }299 else300 {301 break;302 }303 }304 }305 return 0;306 }
View Code

 

 

转载于:https://www.cnblogs.com/ivan-count/p/9358585.html

你可能感兴趣的文章
JS实现类似QQ好友头像hover时显示资料卡的效果
查看>>
离屏渲染优化
查看>>
php 中file_get_contents超时问题的解决方法
查看>>
Oracle 11g RAC oc4j/gsd Offline
查看>>
Ajax下载文件(页面无刷新)
查看>>
[译]Node.js - Event Loop
查看>>
Creating, Stopping, Re-Starting and Deleting a Timer in Oracle Forms
查看>>
laravel 使用 session
查看>>
数据库实例: STOREBOOK > 用户 > 编辑 用户: MGMT_VIEW
查看>>
AjaxPro因为汉字文件夹引发的IE兼容性问题
查看>>
GTK经常使用控件之行编辑( GtkEntry )
查看>>
Picking up Jewels
查看>>
Tween动画TranslateAnimation细节介绍
查看>>
PHP socket 服务器框架集
查看>>
【分词器及自定义】Elasticsearch中文分词器及自定义分词器
查看>>
Ubuntu查看系统版本的方法
查看>>
maven: 打包可运行的jar包(java application)及依赖项处理
查看>>
spark与flume整合
查看>>
数据挖掘工程师笔试及答案整理
查看>>
struts2获取ServletContext对象
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-09 17:32:50   当前IP: 3.144.41.208   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我