本文共 3265 字，大约阅读时间需要 10 分钟。
做题感悟：感觉做多了树链剖分的题目，有很多是树链剖分 + 想法。。
解题思路：
这题非常明显的一点就是 k 非常小，那就是告诉你能够从 k 入手，如何入手呢 ？ 观察能够发现无非最多是 k 类点 ，0 ~ k-1 ,分别表示与根的距离模 k .这样就能够把点分类加权值，可是每一个线段树里存的还是全部元素，查询的时候相应查找。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ;#define INT long long int#define L(x) (x * 2)#define R(x) (x * 2 + 1)const int INF = 0x3f3f3f3f ;const double esp = 0.00000000001 ;const double PI = acos(-1.0) ;const INT mod = 1234567891 ;const int MY = (1<<5) + 5 ;const int MX = 50000 + 5 ;const int S = 20 ;int n ,m ,k ,num ,idx ;int head[MX] ,top[MX] ,siz[MX] ,son[MX] ,dep[MX] ,ti[MX] ,to[MX] ,father[MX] ;struct Edge{ int v ,next ;}E[MX*2] ;void addedge(int u ,int v){ E[num].v = v ; E[num].next = head[u] ;head[u] = num++ ; E[num].v = u ; E[num].next = head[v] ;head[v] = num++ ;}void dfs_find(int u ,int fa){ dep[u] = dep[fa] + 1 ; siz[u] = 1 ; son[u] = 0 ; father[u] = fa ; for(int i = head[u] ;i != -1 ;i = E[i].next) { int v = E[i].v ; if(v == fa) continue ; dfs_find(v ,u) ; siz[u] += siz[v] ; if(siz[son[u]] < siz[v]) son[u] = v ; }}void dfs_time(int u ,int fa){ top[u] = fa ; ti[u] = idx++ ; if(son[u]) dfs_time(son[u] ,top[u]) ; for(int i = head[u] ;i != -1 ;i = E[i].next) { int v = E[i].v ; if(v == son[u] || v == father[u]) continue ; dfs_time(v ,v) ; } to[u] = idx-1 ;}struct node{ int le ,rt ,add ,c ;}T[6][MX*4] ;void push_down(int cnt ,int i){ int& temp = T[cnt][i].add ; if(temp) { T[cnt][L(i)].add += temp ; T[cnt][L(i)].c += temp ; T[cnt][R(i)].add += temp ; T[cnt][R(i)].c += temp ; temp = 0 ; }}void build(int cnt ,int i ,int le ,int rt){ T[cnt][i].le = le ; T[cnt][i].rt = rt ; T[cnt][i].add = T[cnt][i].c = 0 ; if(le == rt) return ; int Mid = (le + rt)>>1 ; build(cnt ,L(i) ,le ,Mid) ; build(cnt ,R(i) ,Mid+1 ,rt) ;}void section(int cnt ,int i ,int le ,int rt ,int val){ if(T[cnt][i].le == le && T[cnt][i].rt == rt) { T[cnt][i].add += val ; T[cnt][i].c += val ; return ; } push_down(cnt ,i) ; int Mid = (T[cnt][i].le + T[cnt][i].rt)>>1 ; if(le > Mid) section(cnt ,R(i) ,le ,rt ,val) ; else if(rt <= Mid) section(cnt ,L(i) ,le ,rt ,val) ; else { section(cnt ,L(i) ,le ,Mid ,val) ; section(cnt ,R(i) ,Mid+1 ,rt ,val) ; }}int Query(int cnt ,int i ,int pos){ if(T[cnt][i].le == T[cnt][i].rt) return T[cnt][i].c ; push_down(cnt ,i) ; int Mid = (T[cnt][i].le + T[cnt][i].rt)>>1 ; if(pos <= Mid) return Query(cnt ,L(i) ,pos) ; // 在左边 else return Query(cnt ,R(i) ,pos) ;}int main(){ //freopen("input.txt" ,"r" ,stdin) ; int Tx ,u ,v ,cnt ,x ,dt ,pos ,val ,cse = 1 ; scanf("%d" ,&Tx) ; while(Tx--) { scanf("%d%d%d" ,&n ,&m ,&k) ; num = 0 ; memset(head ,-1 ,sizeof(head)) ; for(int i = 1 ;i < n ; ++i) { scanf("%d%d" ,&u ,&v) ; addedge(u ,v) ; } dep[1] = siz[0] = 0 ; dfs_find(1 ,1) ; idx = 1 ; dfs_time(1 ,1) ; for(int i = 0 ;i < k ; ++i) build(i ,1 ,1 ,n) ; printf("Case#%d:\n" ,cse++) ; for(int i = 0 ;i < m ; ++i) { scanf("%d%d" ,&pos ,&x) ; if(pos == 1) { scanf("%d" ,&val) ; for(int j = 0 ;j < k ; ++j) { dt = (dep[x] - 1)%k ; // 根所在的集合 cnt = (dt + j)%k ; section(cnt ,1 ,ti[x] ,to[x] ,(j+1)*val) ; } } else printf("%d\n" ,Query((dep[x]-1)%k ,1 ,ti[x])) ; } } return 0 ;}
转载地址：http://znhao.baihongyu.com/