zjoi 2008 树的统计—

比较基础的一道树链剖分的题大概还是得说说思路

　　树链剖分是将树剖成很多条链，比较常见的剖法是按儿子的size来剖分，剖分完后对于这课树的询问用线段树维护——比如求路径和的话——随着他们各自的链向上走，直至他们在同一条链上为止。比较像lca的方法，只不过这里是按链为单位，而且隔壁的SymenYang说可以用树链剖分做lca。。吓哭

　　然后说说惨痛的调题经历：边表一定要开够啊！不是n-1 而是2*（n-1）啊！然后写变量时原始值和映射值要搞清楚啊！不要搞错了！还有就是下次求最小值一定看清下界是多少！树的统计是-30000 ~ 30000 ,我果断naive 的写了一个初值为0！！！ wa 0 就是这么痛苦！还是too Young too Simple !

code :

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct edge{

     int t; edge* next;

 }e[maxn*], *head[maxn];int ne = ;

 void addedge(int f, int t){

     e[ne].t = t; e[ne].next = head[f]; head[f] = e + ne ++;

 }

 int n;

 int size[maxn],fa[maxn],dep[maxn],w[maxn],un[maxn],map[maxn];

 struct node{

     int smax, sum;

     node *l, *r;

 }tr[maxn * ], *root; int trne = ;

 node* build(int l, int r){

     node* x = tr + trne ++;

     if(l != r) {

         int mid = (l + r) >> ;

         x-> l = build(l, mid);

         x-> r = build(mid + , r);

     }

     return x;

 }

 void update(node* x){

     if(x-> l) {

         x-> sum = x-> l-> sum + x-> r->sum;

         x-> smax = max(x-> l-> smax, x-> r-> smax);

     }

 }

 void insert(node* x, int l, int r, int pos, int v) {

     if(l == r) { x-> sum = v, x-> smax = v;}

     else{

         int mid = (l + r) >> ;

         if(pos <= mid) insert(x-> l, l, mid, pos, v);

         else insert(x-> r, mid + , r, pos, v);

         update(x);

     }

 }

 int ask(node* x, int l, int r, int ls, int rs, int flag) {

     if(l == ls && r == rs) {

         if(flag == ) return x-> smax;

         else return x-> sum;

     }

     else {

         int mid = (l + r) >> ;

         if(rs <= mid) return ask(x-> l, l, mid, ls, rs, flag);

         else if(ls >= mid + ) return ask(x-> r, mid + , r, ls, rs, flag);

         else {

             if(flag == )

                 return max(ask(x->l, l, mid, ls, mid, flag), ask(x-> r, mid + , r, mid + , rs, flag));

             else

                 return ask(x-> l, l, mid, ls, mid, flag) + ask(x-> r, mid + , r, mid + , rs, flag);

         }

     }

 }

 int cnt = ;

 void size_cal(int x, int pre) {

     if(pre == -) dep[x] = , fa[x] = x;

     else dep[x] = dep[pre] + , fa[x] = pre;

     size[x] = ;

     for(edge* p = head[x]; p; p = p-> next)

         if(dep[p-> t] == -)size_cal(p-> t, x), size[x] += size[p-> t];

 }

 void divide(int x, int pre){

     if(pre == -) un[x] = x;

     else un[x] = un[pre];

     map[x] = ++ cnt; insert(root, , n, map[x], w[x]);

     int tmax = -, ts = -;

     for(edge* p = head[x]; p; p = p-> next) {

         if(dep[p-> t] > dep[x] && size[p-> t] > tmax) tmax = size[p-> t], ts = p-> t;

     }

     if(ts != -) {

         divide(ts, x);

         for(edge* p = head[x]; p; p = p-> next) {

             if(dep[p-> t] > dep[x] && p-> t != ts) divide(p-> t, -);

         }

     }

 }

 void read() {

     memset(dep,-,sizeof(dep));

     scanf("%d", &n);

     root = build(, n);

     for(int i = ; i <= n - ; i++) {

         int f, t;

         scanf("%d%d", &f, &t);

         addedge(f, t), addedge(t, f);

     }

     for(int i = ; i <= n; ++ i) {

         scanf("%d", &w[i]);

     }

     size_cal(, -);divide(, -);

 }

 int sovmax(int a, int b) {

     int ans = -; int ls, rs;

     while(un[a] != un[b]) {

         if(dep[un[a]] > dep[un[b]]) {

             ls = map[a]; rs = map[un[a]];

             if(ls > rs) swap(ls, rs);

             ans = max(ans, ask(root, , n, ls, rs, ));

             a = fa[un[a]];

         }

         else {

             ls = map[b]; rs = map[un[b]];

             if(ls > rs) swap(ls, rs);

             ans = max(ans, ask(root, , n, ls, rs, ));

             b = fa[un[b]];

             }

     }

     ls = map[a], rs = map[b];

     if(ls > rs) swap(ls,rs);

     ans = max(ans, ask(root, , n, ls, rs, ));

     return ans;

 }

 int sovsum(int a,int b) {

     int ans = ; int ls, rs;

     while(un[a] != un[b]) {

         if(dep[un[a]] > dep[un[b]]) {

             ls = map[a], rs = map[un[a]];

             if(ls > rs) swap(ls, rs);

             ans += ask(root, , n, ls, rs, );

             a = fa[un[a]];

         }

         else {

             ls = map[b]; rs = map[un[b]];

             if(ls > rs) swap(ls, rs);

             ans += ask(root, , n, ls, rs, );

             b = fa[un[b]];

         }

     }

     ls = map[a], rs = map[b];

     if(ls > rs) swap(ls, rs);

     ans += ask(root, , n, ls, rs, );

     return ans;

 }

 void sov() {

     int m;

     scanf("%d", &m);

     while(m --) {

         char s[]; int ls, rs;

         scanf("%s %d%d", s + , &ls, &rs);

         if(s[] == 'M') printf("%d\n", sovmax(ls, rs));

         if(s[] == 'S') printf("%d\n", sovsum(ls, rs));

         if(s[] == 'H') insert(root, , n, map[ls], rs);

     }

 }

 int main(){

     read();sov();

     return ;

 }

巴特西

zjoi 2008 树的统计——树链剖分

最新文章

热门文章