给定 \(n\) 个点和 \(m\) 条边，起点 \(s\) ，每个点有颜色。给定多组 \([l,r]\) ，求最大走 \(l...r\) 边权所有可以走到的不同颜色数之和。（同一种颜色在不同区间内算多组）。 \(n,m\leq 5\times 10^5,q\leq 10^5,type\leq 600\) 。
将原图转换成最小生成树是等效的，因为最大值最小的瓶颈边一定在最小生成树上。于是可以从起点进行 \(DFS\) ,求出到每个点的边权最大，然后存到 \(typ\) 数组中表示同一类型的最优点。最后每次查询答案都直接 \(O(600)\) 暴力得出解。
ll ecnt=1,typ[500005];
piii e[500005];
ll ans[1005],anss;
ll maxn[500005],fa[500005];
ll find(ll x){
return (fa[x]==x)?x:fa[x]=find(fa[x]);
}
struct edge{
ll to,nxt,w;
}ee[1000005];
ll head[500005];
void adde(ll u,ll v,ll w){
ee[++ecnt].nxt=head[u];
ee[ecnt].to=v;
ee[ecnt].w=w;
head[u]=ecnt;
}
void dfs(ll x,ll fa){
for(int i=head[x];i;i=ee[i].nxt){
int y=ee[i].to;
if(y==fa)
continue;
maxn[y]=std::max(maxn[x],ee[i].w);
ans[typ[y]]=std::min(maxn[y],ans[typ[y]]);
dfs(y,x);
}
}
ll n,m,q,x,op,M,las,same=1;
int main(){
n=in(),m=in(),q=in(),x=in(),op=in();
if(op==1)
M=in();
FOR(i,1,n){
typ[i]=in();
fa[i]=i;
}
FOR(i,1,600)
ans[i]=10000000000;
FOR(i,1,m){
ll u=in(),v=in(),w=in();
e[i]=mp(w,mp(u,v));
}
sort(e+1,e+m+1);
FOR(i,1,m){
if(find(e[i].sf)!=find(e[i].ss)){
fa[find(e[i].sf)]=find(e[i].ss);
adde(e[i].sf,e[i].ss,e[i].first);
adde(e[i].ss,e[i].sf,e[i].first);
}
}
ans[typ[x]]=0;
dfs(x,x);
FOR(i,1,q){
anss=0;
ll l=in(),r=in();
if(op==1){
l=(l^las)%M+1;
r=(r^las)%M+1;
}
if(l>r)
std::swap(l,r);
FOR(j,1,600){
if(ans[j]<=r){
anss+=std::min(r-ans[j]+1,r-l+1);
}
}
las=anss;
printf("%lld\n",anss);
}
return 0;
}