思路
设 \(x_i\) 为从 \(a\) 到 \(b\) 的简单路径上的节点， \(y_i\) 从 \(c\) 到 \(d\) 的简单路径上的节点。
那么每次操作就是使 \(x_i\) 的汽油价格和 \(y_i\) 一致，这个东西是具有传递性的，可以用并查集维护。
直接暴力做的复杂度是无法通过本题的。太对不起1024MB的内存了。
考虑维护更多的信息。不明显的，我们可以用并查集维护长度为 \(2^i\) 的段。
具体地，设 \(f2[i][x]\) 表示以 \(x\) 为端点的长度为 \(2^i\) 的向上的段所在的集合， \(f2[i][x+n]\) 表示以 \(x\) 为端点的长度为 \(2^i\) 的向下的段所在的集合。
仍然考虑暴力合并两个长度为 \(2^i\) 的段：
-
若 \(i=0\) 则直接合并两个点。
-
若 \(f2[i][x]\) 和 \(f2[i][y]\) 在同一个集合中，直接退出。
-
否则递归分别合并两个长度 \(2^{i-1}\) 的段，并合并 \(f2[i][x]\) 和 \(f2[i][y]\) 所在的集合。
在实际中合并两个逆向的段和合并两个同向的段略有不同，请读者注意。
暴力合并两个点：
// 合并两个点
void merge(int x,int y){
x=find(x,f1),y=find(y,f1);
if(x==y)return;
ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[x]-L[x]+1)),mod-2)%mod;
ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[y]-L[y]+1)),mod-2)%mod; // 撤销贡献
f1[x]=y;
L[y]=max(L[x],L[y]);
R[y]=min(R[x],R[y]);
ans=1ll*ans*1ll*1ll*max(0ll,1ll*(R[y]-L[y]+1))%mod; // 加上新贡献
}
暴力合并两个长度为 \(2^i\) 的同向段：
// 合并同向等长段
void merge1(int x,int y,int ith){
if(find(x,f2[ith])==find(y,f2[ith]))return; // 剪枝
if(ith==0)return merge(x,y),void(); // 直接合并
f2[ith][find(x,f2[ith])]=find(y,f2[ith]); // 并查集合并
merge1(x,y,ith-1);
merge1(ST[x][ith-1],ST[y][ith-1],ith-1); // 暴力合并两个子段
}
暴力合并两个长度为 \(2^i\) 的逆向段：
// 合并逆向等长段
void merge2(int x,int y,int ith){
if(find(x,f2[ith])==find(y+n,f2[ith]))return; // 剪枝
if(ith==0)return merge(x,y),void();
f2[ith][find(x+n,f2[ith])]=find(y,f2[ith]);// 并查集合并
f2[ith][find(x,f2[ith])]=find(y+n,f2[ith]);
merge2(x,ST[y][ith-1],ith-1); // 与合并同向等长段不同
merge2(ST[x][ith-1],y,ith-1); // 暴力合并两个子段
}
总代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+11,mod=1e9+7;
int ST[MAXN][18],depth[MAXN];
int h[MAXN],nt[MAXN<<1],to[MAXN<<1],linkcnt;
int L[MAXN],R[MAXN],n,ans=1;
int f1[MAXN],f2[18][MAXN<<1];
int ksm(int x,int y){
int cur=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)cur=1ll*cur*x%mod;
return cur;
}
// UNION_FIND_SETS
int find(int u,int *UNION_FIND_SETS){
return UNION_FIND_SETS[u]==u?u:UNION_FIND_SETS[u]=find(UNION_FIND_SETS[u],UNION_FIND_SETS);
}
void link(int u,int v){
nt[++linkcnt]=h[u],h[u]=linkcnt,to[linkcnt]=v;
}
void dfs_init(int u,int father){
depth[u]=depth[father]+1;
f1[u]=u;
for(int i=0; i<=17; i++)
f2[i][u]=u,f2[i][u+n]=u+n;
ST[u][0]=father;
for(int i=1; i<=17; i++)
ST[u][i]=ST[ST[u][i-1]][i-1];
for(int i=h[u]; i; i=nt[i]){
if(to[i]==father)continue;
dfs_init(to[i],u);
}
}
int LCA(int u,int v){
if(depth[u]<=depth[v])swap(u,v);
for(int i=17; i>=0; i--)if(depth[ST[u][i]]>=depth[v])u=ST[u][i];
if(u==v)return u;
for(int i=17; i>=0; i--)if(ST[u][i]!=ST[v][i])u=ST[u][i],v=ST[v][i];
return ST[u][0];
}
int kth_fa(int u,int dist){
for(int i=0; i<=17; i++)
if(((1<<i)&dist))u=ST[u][i];
return u;
}
// 合并两个点
void merge(int x,int y){
x=find(x,f1),y=find(y,f1);
if(x==y)return;
ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[x]-L[x]+1)),mod-2)%mod;
ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[y]-L[y]+1)),mod-2)%mod;
f1[x]=y;
L[y]=max(L[x],L[y]);
R[y]=min(R[x],R[y]);
ans=1ll*ans*1ll*1ll*max(0ll,1ll*(R[y]-L[y]+1))%mod;
}
// 合并同向等长段
void merge1(int x,int y,int ith){
if(find(x,f2[ith])==find(y,f2[ith]))return;
if(ith==0)return merge(x,y),void();
f2[ith][find(x,f2[ith])]=find(y,f2[ith]);
merge1(x,y,ith-1);
merge1(ST[x][ith-1],ST[y][ith-1],ith-1);
}
// 合并逆向等长段
void merge2(int x,int y,int ith){
if(find(x,f2[ith])==find(y+n,f2[ith]))return;
if(ith==0)return merge(x,y),void();
f2[ith][find(x+n,f2[ith])]=find(y,f2[ith]);
f2[ith][find(x,f2[ith])]=find(y+n,f2[ith]);
merge2(x,ST[y][ith-1],ith-1);
merge2(ST[x][ith-1],y,ith-1);
}
int main(){
scanf("%d",&n);
for(int i=2; i<=n; i++){
static int f;
scanf("%d",&f);
link(f,i);
}
dfs_init(1,0);
for(int i=1; i<=n; i++){
scanf("%d %d",&L[i],&R[i]);
ans=1ll*1ll*ans*max(0ll,1ll*(R[i]-L[i]+1))%mod;
}
int Q_sum;
scanf("%d",&Q_sum);
for(int Text=1; Text<=Q_sum; Text++){
int a,b,c,d,lca_of_a_b,lca_of_c_d,T;
scanf("%d %d %d %d",&a,&b,&c,&d);
lca_of_a_b=LCA(a,b);
lca_of_c_d=LCA(c,d);
// 合并同向等长段
T=min(depth[a]-depth[lca_of_a_b],depth[c]-depth[lca_of_c_d]);
for(int i=17; i>=0; i--)if((T&(1<<i)))merge1(a,c,i),a=ST[a][i],c=ST[c][i];
T=min(depth[b]-depth[lca_of_a_b],depth[d]-depth[lca_of_c_d]);
for(int i=17; i>=0; i--)if((T&(1<<i)))merge1(b,d,i),b=ST[b][i],d=ST[d][i];
// 合并逆向等长段
if(a==lca_of_a_b){
T=depth[b]-depth[lca_of_a_b]+1;
for(int i=17; i>=0; i--){
if((T&(1<<i))){
T^=(1<<i);
merge2(b,kth_fa(c,T),i);
b=ST[b][i];
}
}
}
else{
T=depth[a]-depth[lca_of_a_b]+1;
for(int i=17; i>=0; i--){
if((T&(1<<i))){
T^=(1<<i);
merge2(a,kth_fa(d,T),i);
a=ST[a][i];
}
}
}
printf("%d\n",ans);
}
return 0;
}