题解【Gasoline prices】
yizhiming
·
·
题解
算是补充另一篇树上并查集。
Link
题目大意
给定一棵 n 个点的树，每个节点有一个权值区间 [l_i,r_i] 表示这个点的取值范围，有 q 次询问，每次给定 a,b,c,d，表示要求 a\rightarrow b 的路径点的权值与 c\rightarrow d 的权值对应相等，并求出满足条件的方案数，对 10^9+7 取模，要注意询问之间不独立。
## 题目分析
首先这个题是一个[序列问题](https://www.luogu.com.cn/problem/P3295)转换成的，建议先去做一下这道题。
这篇题解是补充，故不详细解释，将上面的序列问题转换成树上，原本的倍增形式由序列下标，变成了树上倍增祖先，所以问题就相当于将查询分成若干条链，对每部分进行并查集维护即可。
不难发现由于两条路径的长度需要一样，那么将两个点都尽可能地往上跳，对于这部分，我们需要将两段路径正序合并起来，处理完这一部分后，一定会有一个端点在路径顶端，所以对于其中一个路径往上倍增跳，这部分是倒序合并，所以要维护两个方向的并查集。
这道题还有一个不同就是每次修改都要输出方案，而上面那道题只需要输出一次，所以考虑每次修改的时候递归下去，若当前区间已经被合并了则退出，否则拆成两个小区间接着递归，直到单点的时候，求个逆元将原贡献去掉，再算上新贡献即可。
考虑一共只有 $n\log n$ 个不同的并查集，所以这部分复杂度正确。
## Code
这部分才是精华，我怎么调代码都会超时，改着改着就变成了另外一篇题解的样子，后来才发现那篇也会超时。。。
首先在并查集查询的时候不传当前层数，而传当前层数的对应数组的指针，虽然不知道为什么但是这样会变快。
因为有倍增，所以请将并查集和树上的倍增数组的较小的一维移到前面。
还有最为关键的一点，只路径压缩并查集的话，复杂度是 $O(n\log^2 n)$ 的，在阴间数据下会超时，所以要额外加上按秩合并，将复杂度优化成 $O(n\log n \alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数，原谅我不知道这玩意怎么打。
```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
//#define int long long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N = 2e5+5;
int Mod = 1e9+7;
int f[20][N*2],fa[20][N],siz[20][N],K = 17,n,m;//f并查集，fa树上
int head[N],tote,ans;
struct aa{
int nxt,to;
}edge[N*2];
void link(int u,int v){
edge[++tote].nxt = head[u];edge[tote].to = v;head[u] = tote;
}
int ksm(int x,int y){
int res = 1;
while(y){
if(y&1){
res = (1ll*res*x)%Mod;
}
x = (1ll*x*x)%Mod;
y>>=1;
}
return res;
}
int dep[N],L[N],R[N];
void dfs(int u){
for(int i=head[u];i;i=edge[i].nxt){
int now = edge[i].to;
fa[0][now] = u;
dep[now] = dep[u]+1;
dfs(now);
}
}
int Lca(int x,int y){
if(x==y){
return x;
}
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=K;i>=0;i--){
if(dep[fa[i][x]]>=dep[y]){
x = fa[i][x];
}
}
if(x==y){
return x;
}
for(int i=K;i>=0;i--){
if(fa[i][x]!=fa[i][y]){
x = fa[i][x];y = fa[i][y];
}
}
return fa[0][x];
}
int find(int x,int *ff){
if(ff[x]!=x){
ff[x] = find(ff[x],ff);
}
return ff[x];
}
int getfa(int x,int k){
for(int i=K;i>=0;i--){
if((k>>i)&1){
x = fa[i][x];
}
}
return x;
}
void hb(int x,int y,int k){
x = find(x,f[k]);y = find(y,f[k]);
if(siz[k][x]>siz[k][y]){
swap(x,y);
}
siz[k][y]+=(siz[k][x]==siz[k][y]);
f[k][x] = y;
}
void mer(int x,int y){
x = find(x,f[0]);y = find(y,f[0]);
if(x==y){
return;
}
// cout<<"XY:"<<L[x]<<" "<<R[x]<<" "<<L[y]<<" "<<R[y]<<" "<<ans<<" "<<x<<" "<<y<<"\n";
ans = 1ll*ans*ksm(R[x]-L[x]+1,Mod-2)%Mod;
ans = 1ll*ans*ksm(R[y]-L[y]+1,Mod-2)%Mod;
if(siz[0][x]>siz[0][y]){
swap(x,y);
}
f[0][x] = y;
L[y] = max(L[y],L[x]);
R[y] = min(R[y],R[x]);
ans = 1ll*ans*max(0ll,1ll*(R[y]-L[y]+1))%Mod;
}
void merge1(int x,int y,int k){
int u = find(x,f[k]),v = find(y,f[k]);
if(u==v){
return;
}
if(k==0){
mer(x,y);
return;
}
hb(x,y,k);
// f[k][u] = v;
merge1(x,y,k-1);
merge1(fa[k-1][x],fa[k-1][y],k-1);
}
void merge2(int x,int y,int k){
if(find(x,f[k])==find(y+n,f[k])){
return;
}
if(k==0){
mer(x,y);
return;
}
hb(x,y+n,k);
hb(x+n,y,k);
// f[k][find(x,f[k])] = find(y+n,f[k]);
// f[k][find(x+n,f[k])] = find(y,f[k]);
merge2(x,fa[k-1][y],k-1);
merge2(fa[k-1][x],y,k-1);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = read();
for(int i=2;i<=n;i++){
int x = read();
link(x,i);
}
ans = 1;
for(int i=1;i<=n;i++){
L[i] = read();R[i] = read();
ans = 1ll*ans*max(0ll,1ll*(R[i]-L[i]+1))%Mod;
}
// cout<<"ANS:"<<ans<<"\n";
dep[1] = 1;
dfs(1);
for(int j=1;j<=K;j++){
for(int i=1;i<=n;i++){
fa[j][i] = fa[j-1][fa[j-1][i]];
}
}
for(int i=0;i<=K;i++){
for(int j=1;j<=n;j++){
f[i][j] = j;
f[i][j+n] = j+n;
siz[i][j] = 1;
siz[i][j+n] = 1;
}
}
m = read();
int a,b,c,d;
while(m--){
a = read();b = read();c = read();d = read();
if(!ans){
cout<<0<<"\n";
continue;
}
int L1 = Lca(a,b),L2 = Lca(c,d);
int k = min(dep[a]-dep[L1],dep[c]-dep[L2]);
// cout<<"LCA:"<<L1<<" "<<L2<<"\n";
// cout<<"K1:"<<k<<"\n";
for(int i=K;i>=0;i--){
if((k>>i)&1){
merge1(a,c,i);
a = fa[i][a];
c = fa[i][c];
}
}
k = min(dep[b]-dep[L1],dep[d]-dep[L2]);
// cout<<"K2:"<<k<<"\n";
for(int i=K;i>=0;i--){
if((k>>i)&1){
merge1(b,d,i);
b = fa[i][b];
d = fa[i][d];
}
}
if(a==L1){
k = dep[b]-dep[L1]+1;
for(int i=K;i>=0;i--){
if((k>>i)&1){
k^=(1<<i);
merge2(b,getfa(c,k),i);
b = fa[i][b];
}
}
}else{
k = dep[a]-dep[L1]+1;
for(int i=K;i>=0;i--){
if((k>>i)&1){
k^=(1<<i);
merge2(a,getfa(d,k),i);
a = fa[i][a];
}
}
}
cout<<ans<<"\n";
}
return 0;
}
```
和那篇题解的作者聊了一下，认为是评测机波动卡掉了他的代码。
很久之前交了没过审，才想起来重交一遍。