题目分析：
观察题目发现度数不小于三，考虑从边分治入手，用点分治代替。将树划分成重心链接的结构，称为点分树。令当前询问的点为$ u $。那么我们考虑点分树的根到$ u $的一条路径。考虑根结点，排除掉与$ u $有关的点所在的子树，剩下的点到$ u $的路径长度等价于它们到根的路径加上根到$ u $的路径。所以我们要做的是消去$ u $所在子树的影响，然后递归问题。这个做法在点分治意义下是常用做法，前缀和维护即可。由于每个点都在点分路径上的前缀和上出现了一次，而点分树高为$ O(log n) $，所以空间为$ O(n*log n) $。时间是$ O(n*log^2n) $
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 150005; 5 6 int n,Q,A; 7 8 int x[maxn]; 9 10 vector <pair<int,int> > g[maxn]; 11 int euler[maxn<<1],nE,app[maxn][2]; 12 int RMQ[maxn<<1][19],f[maxn],dep[maxn],climb[maxn]; 13 14 template<typename T> 15 void in(T &x){ 16 x = 0; char ch = getchar(); 17 while(ch > '9' || ch < '0') ch = getchar(); 18 while(ch >= '0' && ch <= '9') x = x*10+ch-'0',ch=getchar(); 19 } 20 21 void dfs(int now,int last,int dp,int cl){ 22 dep[now] = dp; f[now] = last; climb[now] = cl; 23 euler[++nE] = now; app[now][0] = app[now][1] = nE; 24 for(int i=0;i<g[now].size();i++){ 25 int pp = g[now][i].first,len = g[now][i].second; 26 if(pp == last) continue; 27 dfs(pp,now,dp+len,cl+1); 28 euler[++nE] = now; app[now][1] = nE; 29 } 30 } 31 32 void BuildRMQ(){ 33 for(int i=1;i<=nE;i++) RMQ[i][0] = euler[i]; 34 for(int k=1;(1<<k)<=nE;k++){ 35 for(int i=1;i<=nE;i++){ 36 if(i+(1<<k-1) > nE) {RMQ[i][k] = RMQ[i][k-1];continue;} 37 if(climb[RMQ[i][k-1]] < climb[RMQ[i+(1<<k-1)][k-1]]){ 38 RMQ[i][k] = RMQ[i][k-1]; 39 }else RMQ[i][k] = RMQ[i+(1<<k-1)][k-1]; 40 } 41 } 42 } 43 44 int QueryLCA(int u,int v){ 45 int fst = min(app[u][0],app[v][0]),sec = max(app[u][1],app[v][1]); 46 int len = sec-fst+1,k = 0; 47 while((1<<k+1) <= len) k++; 48 if(climb[RMQ[fst][k]] < climb[RMQ[sec-(1<<k)+1][k]]) return RMQ[fst][k]; 49 else return RMQ[sec-(1<<k)+1][k]; 50 } 51 52 int dist(int u,int v){ return dep[u]+dep[v]-2*dep[QueryLCA(u,v)]; } 53 54 class Pdivide{ 55 private: 56 int sz[maxn],arr[maxn],seg[maxn],fa[maxn]; 57 vector <pair<int,int> > v[maxn],v2[maxn]; 58 vector <long long> sum[maxn],sum2[maxn]; 59 stack <int> sta; 60 void GetSize(int now,int last){ 61 sz[now] = 0;seg[now] = 0; 62 for(int i=0;i<g[now].size();i++){ 63 int pp = g[now][i].first; 64 if(arr[pp] || pp == last) continue; 65 GetSize(pp,now); 66 sz[now] += sz[pp]; 67 seg[now] = max(seg[now],sz[pp]); 68 } 69 sz[now]++; 70 } 71 int GetG(int now,int last,int tot){ 72 int res = now; seg[now] = max(seg[now],tot-sz[now]-1); 73 for(int i=0;i<g[now].size();i++){ 74 int pp = g[now][i].first; 75 if(arr[pp] || pp == last) continue; 76 int p = GetG(pp,now,tot); 77 if(seg[p] < seg[res]) res = p; 78 } 79 return res; 80 } 81 void LenQuery(int now,int last,int dst,int root,int oldroot){ 82 v[root].push_back(make_pair(x[now],dst)); 83 if(oldroot != 0) v2[root].push_back(make_pair(x[now],dist(now,oldroot))); 84 for(int i=0;i<g[now].size();i++){ 85 int pp = g[now][i].first, len = g[now][i].second; 86 if(arr[pp] || pp == last) continue; 87 LenQuery(pp,now,dst+len,root,oldroot); 88 } 89 } 90 void divide(int now,int last,int ht){ 91 GetSize(now,0); 92 int p = GetG(now,0,sz[now]); 93 94 LenQuery(p,0,0,p,last); sort(v[p].begin(),v[p].end()); sum[p].push_back(0); 95 sort(v2[p].begin(),v2[p].end()); sum2[p].push_back(0); 96 for(int i=0;i<v[p].size();i++) sum[p].push_back(sum[p][i]+1ll*v[p][i].second); 97 for(int i=0;i<v2[p].size();i++) sum2[p].push_back(sum2[p][i]+1ll*v2[p][i].second); 98 99 fa[p] = last;arr[p] = ht; 100 for(int i=0;i<g[p].size();i++){ 101 int nxt = g[p][i].first; 102 if(arr[nxt]) continue; 103 divide(nxt,p,ht+1); 104 } 105 } 106 107 public: 108 void BuildTree(){divide(1,0,1);} 109 void printans(int now,int l,int r,long long &lastans){ 110 int p = now; 111 while(p != 0) sta.push(p),p = fa[p]; 112 long long ans = 0; 113 while(!sta.empty()){ 114 int tp = sta.top();sta.pop(); 115 int pp = lower_bound(v[tp].begin(),v[tp].end(),make_pair(l,0))-v[tp].begin(); 116 if(pp == v[tp].size()||v[tp][pp].first > r) break; 117 int ed = upper_bound(v[tp].begin(),v[tp].end(),make_pair(r,(int)1E9))-v[tp].begin()-1; 118 int len = ed-pp+1; 119 ans += sum[tp][ed+1] - sum[tp][pp] + 1ll*len*dist(tp,now); 120 if(fa[tp]!=0) 121 ans -= (sum2[tp][ed+1] - sum2[tp][pp] + 1ll*len*dist(fa[tp],now)); 122 } 123 while(!sta.empty())sta.pop(); 124 printf("%lld ",ans);lastans = ans; 125 } 126 }T1; 127 128 void init(){ 129 dfs(1,0,0,1); 130 BuildRMQ(); 131 T1.BuildTree(); 132 } 133 134 void work(){ 135 long long lastans = 0; 136 for(int i=1;i<=Q;i++){ 137 int a,u,v; in(a),in(u),in(v); 138 u = (1ll*u+lastans)%A; 139 v = (1ll*v+lastans)%A; 140 if(u > v) swap(u,v); 141 T1.printans(a,u,v,lastans); 142 } 143 } 144 145 int main(){ 146 in(n),in(Q),in(A); 147 for(int i=1;i<=n;i++) in(x[i]); 148 for(int i=1;i<n;i++){ 149 int u,v,w; in(u),in(v),in(w); 150 g[u].push_back(make_pair(v,w)); 151 g[v].push_back(make_pair(u,w)); 152 } 153 init(); 154 work(); 155 return 0; 156 }