如果还没有做过幻想乡战略游戏的话，可以先到这里看看
这道题与幻想乡战略游戏的计算代价那一步的实质其实是一样的。
我们建好点分树，维护这三个东西：
$sumD:$当前点对应的分治范围内年龄在$[L,R]$的妖怪的数量
$sumV:$当前点对应的分治范围年龄在$[L,R]$的妖怪到达分治中心的距离总和
$upV:$当前点对应的分治范围年龄在$[L,R]$的妖怪到达分支中心的父亲的距离总和
然后跟上面那道题一样用类似于容斥和拼凑的方法就可以计算出每一次询问的答案了。
那么问题又来了：怎么维护分治范围内年龄在$[L,R]$的妖怪的数量和距离？
这么考虑：将当前点对应的分治范围内所有点拿出来，按照年龄排序，对距离做前缀和，每一次查询的时候在年龄对应的数组上二分出位置即可。空间复杂度是$O(nlogn)$的
那么我们就在$O(Qlog^2n)$的时间复杂度内完成了这道题
1 #include<bits/stdc .h> 2 #define int long long 3 #define INF 0x7fffffff 4 #define P pair < int , int > 5 //This code is written by Itst 6 using namespace std; 7 8 inline int read(){ 9 int a = 0; 10 bool f = 0; 11 char c = getchar(); 12 while(c != EOF && !isdigit(c)){ 13 if(c == '-') 14 f = 1; 15 c = getchar(); 16 } 17 while(c != EOF && isdigit(c)){ 18 a = (a << 3) (a << 1) (c ^ '0'); 19 c = getchar(); 20 } 21 return f ? -a : a; 22 } 23 24 const int MAXN = 150010; 25 struct Edge{ 26 int end , upEd , len; 27 }Ed[MAXN << 1]; 28 int head[MAXN] , age[MAXN] , fa[MAXN] , size[MAXN] , len[MAXN]; 29 int ST[21][MAXN << 1] , fir[MAXN] , dep[MAXN] , logg2[MAXN << 1]; 30 int N , Q , A , cntEd , ts , nowSize , minSize , minInd; 31 vector < P > cur[MAXN]; 32 vector < int > up[MAXN]; 33 bool vis[MAXN]; 34 35 inline int abss(int a){ 36 return a < 0 ? -a : a; 37 } 38 39 bool cmpp(P a , P b){ 40 return age[a.first] < age[b.first]; 41 } 42 43 void addEd(int , int , int); 44 void getSize(int); 45 void getRoot(int); 46 void init_dfz(int , int); 47 void init_dfs(int , int , int); 48 int cmp(int , int); 49 void init_st(); 50 void init(); 51 int LCA(int , int); 52 int calcLen(int , int); 53 int query(int , int , int); 54 55 signed main(){ 56 #ifndef ONLINE_JUDGE 57 freopen("3241.in" , "r" , stdin); 58 //freopen("3241.out" , "w" , stdout); 59 #endif 60 N = read(); 61 Q = read(); 62 A = read(); 63 for(int i = 1 ; i <= N ; i) 64 age[i] = read(); 65 for(int i = 1 ; i < N ; i){ 66 int a = read() , b = read() , c = read(); 67 addEd(a , b , c); 68 addEd(b , a , c); 69 } 70 init(); 71 int lastans = 0; 72 for(int i = 1 ; i <= Q ; i){ 73 int u = read() , a = read() , b = read(); 74 a = (a lastans) % A; 75 b = (b lastans) % A; 76 if(a > b) 77 swap(a , b); 78 printf("%lld\n" , lastans = query(u , a , b)); 79 } 80 return 0; 81 } 82 83 inline void addEd(int a , int b , int c){ 84 Ed[ cntEd].end = b; 85 Ed[cntEd].upEd = head[a]; 86 Ed[cntEd].len = c; 87 head[a] = cntEd; 88 } 89 90 void getSize(int x){ 91 vis[x] = 1; 92 nowSize; 93 for(int i = head[x] ; i ; i = Ed[i].upEd) 94 if(!vis[Ed[i].end]) 95 getSize(Ed[i].end); 96 vis[x] = 0; 97 } 98 99 void getRoot(int x){100 vis[x] = size[x] = 1;101 int maxN = 0;102 for(int i = head[x] ; i ; i = Ed[i].upEd)103 if(!vis[Ed[i].end]){104 getRoot(Ed[i].end);105 maxN = max(maxN , size[Ed[i].end]);106 size[x] = size[Ed[i].end];107 }108 maxN = max(maxN , nowSize - size[x]);109 if(maxN < minSize){110 minSize = maxN;111 minInd = x;112 }113 vis[x] = 0;114 }115 116 117 void init_dfs(int x , int f , int l){118 dep[x] = dep[f] 1;119 fir[x] = ts;120 len[x] = l;121 ST[0][ts] = x;122 for(int i = head[x] ; i ; i = Ed[i].upEd)123 if(Ed[i].end != f){124 init_dfs(Ed[i].end , x , l Ed[i].len);125 ST[0][ ts] = x;126 }127 }128 129 inline int cmp(int x , int y){130 return dep[x] < dep[y] ? x : y;131 }132 133 void init_st(){134 for(int i = 2 ; i <= N << 1 ; i)135 logg2[i] = logg2[i >> 1] 1;136 for(int i = 1 ; 1 << i <= N << 1 ; i)137 for(int j = 1 ; j (1 << i) <= N << 1 ; j)138 ST[i][j] = cmp(ST[i - 1][j] , ST[i - 1][j (1 << (i - 1))]);139 }140 141 inline int LCA(int x , int y){142 x = fir[x];143 y = fir[y];144 if(y < x)145 swap(x , y);146 int t = logg2[y - x 1];147 return cmp(ST[t][x] , ST[t][y - (1 << t) 1]);148 }149 150 inline int calcLen(int x , int y){151 return len[x] len[y] - (len[LCA(x , y)] << 1);152 }153 154 void init_dfz(int x , int p){155 nowSize = 0;156 minSize = INF;157 getSize(x);158 getRoot(x);159 x = minInd;160 fa[x] = p;161 vis[x] = 1;162 for(int i = x ; i ; i = fa[i])163 cur[i].push_back(P(x , 0));164 for(int i = head[x] ; i ; i = Ed[i].upEd)165 if(!vis[Ed[i].end])166 init_dfz(Ed[i].end , x);167 sort(cur[x].begin() , cur[x].end() , cmpp);168 up[x].push_back(calcLen(cur[x][0].first , fa[x] ? fa[x] : x));169 cur[x][0].second = calcLen(cur[x][0].first , x);170 cur[x][0].first = age[cur[x][0].first];171 for(int i = 1 ; i < cur[x].size() ; i){172 up[x].push_back(up[x][i - 1] calcLen(cur[x][i].first , fa[x] ? fa[x] : x));173 cur[x][i].second = cur[x][i - 1].second calcLen(cur[x][i].first , x);174 cur[x][i].first = age[cur[x][i].first];175 }176 vis[x] = 0;177 }178 179 void init(){180 init_dfs(1 , 0 , 0);181 init_st();182 init_dfz(1 , 0);183 }184 185 186 inline int query(int x , int l , int r){187 int sum = 0 , p = x , pastSum = 0 , pastNum = 0 , curSum , curNum;188 while(x){189 int t1 = lower_bound(cur[x].begin() , cur[x].end() , P(l , -1)) - cur[x].begin() , t2 = lower_bound(cur[x].begin() , cur[x].end() , P(r 1 , -1)) - cur[x].begin();190 curSum = 0;191 curNum = t2 - t1;192 if(--t1 >= 0)193 curSum -= cur[x][t1].second;194 if(--t2 >= 0)195 curSum = cur[x][t2].second;196 sum = curSum - pastSum;197 sum = calcLen(p , x) * (curNum - pastNum);198 pastSum = 0;199 if(t1 >= 0)200 pastSum -= up[x][t1];201 if(t2 >= 0)202 pastSum = up[x][t2];203 pastNum = curNum;204 x = fa[x];205 }206 return sum;207 }来源：http://www.icode9.com/content-4-89051.html
联系客服
