点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005];
int p[100005],n;
int dfn[100005],e[200005],tot,cnt,s[100005],z[100005],id[100005],h[100005],w[100005],d[100005],fa[100005],raw[100005],pos[100005];
struct t1
{
int l,r,minn,maxn;
}t[400005];
struct f1
{
int l,r,dfn,pos1,pos2;
}f[400005];
void buildt(int p,int l,int r)
{
t[p].l=l;
t[p].r=r;
if(l==r)
{
t[p].minn=t[p].maxn=w[l];
return;
}
int mid=(l+r)>>1;
buildt(p*2,l,mid);
buildt(p*2+1,mid+1,r);
t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
}
void buildf(int p,int l,int r)
{
f[p].l=l;
f[p].r=r;
if(l==r)
{
f[p].dfn=f[p].pos1=f[p].pos2=raw[l];
return;
}
int mid=(l+r)>>1;
buildf(p*2,l,mid);
buildf(p*2+1,mid+1,r);
f[p].dfn=(dfn[f[p*2].dfn]>dfn[f[p*2+1].dfn])*f[p*2].dfn+(dfn[f[p*2].dfn]<dfn[f[p*2+1].dfn])*f[p*2+1].dfn;
f[p].pos1=(pos[f[p*2].pos1]<pos[f[p*2+1].pos1])*f[p*2].pos1+(pos[f[p*2].pos1]>pos[f[p*2+1].pos1])*f[p*2+1].pos1;
f[p].pos2=(pos[f[p*2].pos2]>pos[f[p*2+1].pos2])*f[p*2].pos2+(pos[f[p*2].pos2]<pos[f[p*2+1].pos2])*f[p*2+1].pos2;
}
void changef(int p,int x)
{
if(f[p].l==f[p].r)
{
f[p].dfn=f[p].pos1=f[p].pos2=raw[x];
return;
}
int mid=(f[p].l+f[p].r)>>1;
if(x<=mid)
{
changef(p*2,x);
}
else
{
changef(p*2+1,x);
}
f[p].dfn=(dfn[f[p*2].dfn]>dfn[f[p*2+1].dfn])*f[p*2].dfn+(dfn[f[p*2].dfn]<dfn[f[p*2+1].dfn])*f[p*2+1].dfn;
f[p].pos1=(pos[f[p*2].pos1]<pos[f[p*2+1].pos1])*f[p*2].pos1+(pos[f[p*2].pos1]>pos[f[p*2+1].pos1])*f[p*2+1].pos1;
f[p].pos2=(pos[f[p*2].pos2]>pos[f[p*2+1].pos2])*f[p*2].pos2+(pos[f[p*2].pos2]<pos[f[p*2+1].pos2])*f[p*2+1].pos2;
}
void changet(int p,int x,int va)
{
if(t[p].l==t[p].r)
{
t[p].minn=t[p].maxn=va;
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid)
{
changet(p*2,x,va);
}
else
{
changet(p*2+1,x,va);
}
t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
}
int askminn(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)
{
return t[p].minn;
}
int mid=(t[p].l+t[p].r)>>1,va=INT_MAX;
if(l<=mid)
{
va=min(va,askminn(p*2,l,r));
}
if(r>mid)
{
va=min(va,askminn(p*2+1,l,r));
}
return va;
}
int askmaxn(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)
{
return t[p].maxn;
}
int mid=(t[p].l+t[p].r)>>1,va=0;
if(l<=mid)
{
va=max(va,askmaxn(p*2,l,r));
}
if(r>mid)
{
va=max(va,askmaxn(p*2+1,l,r));
}
return va;
}
int askdfn(int p,int l,int r)
{
if(l<=f[p].l&&r>=f[p].r)
{
return f[p].dfn;
}
int mid=(f[p].l+f[p].r)>>1,va=0;
if(l<=mid)
{
va=askdfn(p*2,l,r);
}
if(r>mid)
{
if(!va)
{
va=askdfn(p*2+1,l,r);
}
else
{
int tmp=askdfn(p*2+1,l,r);
if(dfn[va]<dfn[tmp])
{
va=tmp;
}
}
}
return va;
}
int askpos1(int p,int l,int r)
{
if(l<=f[p].l&&r>=f[p].r)
{
return f[p].pos1;
}
int mid=(f[p].l+f[p].r)>>1,va=0;
if(l<=mid)
{
va=askpos1(p*2,l,r);
}
if(r>mid)
{
if(!va)
{
va=askpos1(p*2+1,l,r);
}
else
{
int tmp=askpos1(p*2+1,l,r);
if(pos[va]>pos[tmp])
{
va=tmp;
}
}
}
return va;
}
int askpos2(int p,int l,int r)
{
if(l<=f[p].l&&r>=f[p].r)
{
return f[p].pos2;
}
int mid=(f[p].l+f[p].r)>>1,va=0;
if(l<=mid)
{
va=askpos2(p*2,l,r);
}
if(r>mid)
{
if(!va)
{
va=askpos2(p*2+1,l,r);
}
else
{
int tmp=askpos2(p*2+1,l,r);
if(pos[va]<pos[tmp])
{
va=tmp;
}
}
}
return va;
}
void dfs1(int n1)
{
s[n1]=1;
dfn[n1]=++tot;
e[++cnt]=n1;
z[n1]=0;
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa[n1])
{
d[a[n1][i]]=d[n1]+1;
fa[a[n1][i]]=n1;
dfs1(a[n1][i]);
e[++cnt]=n1;
s[n1]+=s[a[n1][i]];
if(s[a[n1][i]]>s[z[n1]])
{
z[n1]=a[n1][i];
}
}
}
}
void dfs2(int n1)
{
id[n1]=++tot;
w[tot]=p[n1];
if(z[n1])
{
h[z[n1]]=h[n1];
dfs2(z[n1]);
}
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa[n1]&&a[n1][i]!=z[n1])
{
h[a[n1][i]]=a[n1][i];
dfs2(a[n1][i]);
}
}
}
int getminn(int u,int v)
{
int minn=INT_MAX;
while(h[u]!=h[v])
{
if(d[h[u]]<d[h[v]])
{
swap(u,v);
}
minn=min(minn,askminn(1,id[h[u]],id[u]));
u=fa[h[u]];
}
minn=min(minn,askminn(1,min(id[u],id[v]),max(id[u],id[v])));
return minn;
}
int getmaxn(int u,int v)
{
int maxn=0;
while(h[u]!=h[v])
{
if(d[h[u]]<d[h[v]])
{
swap(u,v);
}
maxn=max(maxn,askmaxn(1,id[h[u]],id[u]));
u=fa[h[u]];
}
maxn=max(maxn,askmaxn(1,min(id[u],id[v]),max(id[u],id[v])));
return maxn;
}
int getlen(int u,int v)
{
int len=0;
while(h[u]!=h[v])
{
if(d[h[u]]<d[h[v]])
{
swap(u,v);
}
len=len+d[u]-d[fa[h[u]]];
u=fa[h[u]];
}
len=len+abs(d[u]-d[v]);
return len;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
a[i].clear();
cin>>p[i];
raw[p[i]]=i;
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
cnt=tot=0;
d[1]=1;
fa[1]=0;
dfs1(1);
tot=0;
dfs2(1);
for(int i=1;i<=cnt;i++)
{
pos[e[i]]=i;
}
buildt(1,1,n);
buildf(1,1,n);
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
int opt,u,v;
cin>>opt>>u>>v;
if(opt==1)
{
changet(1,id[u],w[id[v]]);
changet(1,id[v],w[id[u]]);
swap(w[id[u]],w[id[v]]);
raw[p[u]]=v;
changef(1,p[u]);
raw[p[v]]=u;
changef(1,p[v]);
swap(p[u],p[v]);
}
else
{
int x=askpos1(1,u,v);
int y=askdfn(1,u,v);
if(x==y)
{
x=askpos2(1,u,v);
}
int len=getlen(x,y);
if(len==v-u&&getmaxn(x,y)==v&&getminn(x,y)==u)
{
cout<<"Yes"<<"\n";
}
else
{
cout<<"No"<<"\n";
}
}
}
}
return 0;
}
/*
1
9
3 4 9 5 1 2 7 6 8
1 2
2 3
2 4
2 5
1 6
6 7
7 8
7 9
*/