「YNOI2016」这是我自己的发明

震惊!我妻由乃当上了发明家!!!

传送门

洛谷P4689

BZOJ4940

题解

又是一道由乃OI的毒瘤题QwQ。

前置技能,这题的简化版:SNOI2017 一个简单的询问

做完上面一题,不难发现,只要爬到树上做这题就行了。

一巴掌把树拍扁按照DFS序将树化成一个序列,这样每一颗子树对应着序列上的一段区间,然后就和之前那一题没什么区别了。

但是!!!竟然有换根这种操作。

不过不难发现,其实换根的操作就是假的。

先设当前的根为$rt$,询问子树的节点为$x$,不管怎样,我们就认为根始终是节点$1$。

然后又这么几种情况:

  • $x=rt​$

此时询问的就是整棵树。

1.png

  • $LCA(x,rt)\neq x$

此时查询的就是当$1$为根时$x$的子树。

2.png

  • $LCA(x,rt)=x​$

3.png

此时查询整棵树除去rt到x路径上离x最近的一个节点(就是图中好几个箭头指的那个点)的子树。可以拆成两个序列解决。那个节点可以通过倍增找到。

拆分成若干个序列之后,直接莫队即可。

还有记得要离散,权值是比较大的。我就因为没看数据范围,忘记离散,结果崩掉1个点QwQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005,maxm=500005;
int n,m,q,rt,idx,tot,lnk[maxn],son[maxn*2],nxt[maxn*2],St[maxn],En[maxn],father[maxn][20],dep[maxn],A[maxn],B[maxn],S,Area[maxn],num,cnt1[maxn],cnt2[maxn],p1,p2;LL ans[maxm],now; //要开的东西实在太多,写的好丑QwQ
map<int,int> hsh;
inline int read()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
void Build(int now,int fa) //以节点1作为根节点初始化
{
father[now][0]=fa;dep[now]=dep[fa]+1;idx++;A[idx]=B[now];St[now]=idx;
for(int i=1;i<=16;i++) father[now][i]=father[father[now][i-1]][i-1];
for(int i=lnk[now];i;i=nxt[i])
if(son[i]!=fa)
Build(son[i],now);
En[now]=idx;
}
int LCA(int u,int v) //倍增LCA
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=16;i>=0;i--) if(dep[father[u][i]]>=dep[v]) u=father[u][i];
for(int i=16;i>=0;i--) if(father[u][i]!=father[v][i]){u=father[u][i];v=father[v][i];}
if(u!=v) return father[u][0];
return u;
}
int GetSon(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=16;i>=0;i--) if(dep[father[u][i]]>dep[v]) u=father[u][i];
return u;
}
struct Interval
{
int R1,R2,f,id;
void Init(){if(R1>R2)swap(R1,R2);}
bool operator < (const Interval& b)const{return Area[R1]<Area[b.R1]||(Area[R1]==Area[b.R1]&&((Area[R1]&1)?R2<b.R2:R2>b.R2));}
}Q[maxm*16]; //注意一个询问最左可以拆成16个区间
inline void Add(int L1,int R1,int L2,int R2,int id)
{
num++;Q[num].R1=R1;Q[num].R2=R2;Q[num].f=1;Q[num].Init();Q[num].id=id;
if(L1>1){num++;Q[num].R1=L1-1;Q[num].R2=R2;Q[num].f=-1;Q[num].Init();Q[num].id=id;}
if(L2>1){num++;Q[num].R1=R1;Q[num].R2=L2-1;Q[num].f=-1;Q[num].Init();Q[num].id=id;}
if(L1>1&&L2>1){num++;Q[num].R1=L1-1;Q[num].R2=L2-1;Q[num].f=1;Q[num].Init();Q[num].id=id;}
}
int main()
{
n=read();m=read();S=sqrt(n)+1e-10;rt=1;
for(int i=1;i<=n;i++) A[i]=B[i]=read();
sort(B+1,B+1+n);int tep=0;
for(int i=1;i<=n;i++) if(!hsh[B[i]]) hsh[B[i]]=++tep;
for(int i=1;i<=n;i++) B[i]=hsh[A[i]]; //离散
for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
for(int i=1;i<n;i++)
{
int a=read(),b=read();
add_e(a,b);add_e(b,a);
}
Build(1,0);
for(int i=1;i<=m;i++)
{
if(read()==1) rt=read();
else
{
int x=read(),y=read();q++;
int len1=0,L1[3],R1[3],len2=0,L2[3],R2[3];
if(x==rt){len1++;L1[len1]=1;R1[len1]=n;}
else if(LCA(x,rt)!=x){len1++;L1[len1]=St[x];R1[len1]=En[x];}
else{int v=GetSon(rt,x);len1++;L1[len1]=1;R1[len1]=St[v]-1;if(En[v]<n){len1++;L1[len1]=En[v]+1;R1[len1]=n;}}
if(y==rt){len2++;L2[len2]=1;R2[len2]=n;}
else if(LCA(y,rt)!=y){len2++;L2[len2]=St[y];R2[len2]=En[y];}
else{int v=GetSon(rt,y);len2++;L2[len2]=1;R2[len2]=St[v]-1;if(En[v]<n){len2++;L2[len2]=En[v]+1;R2[len2]=n;}}
for(int j=1;j<=len1;j++)
for(int k=1;k<=len2;k++)
Add(L1[j],R1[j],L2[k],R2[k],q); //拆成区间上莫队
}
}
sort(Q+1,Q+1+num); //莫队
for(int i=1;i<=num;i++)
{
while(p2<Q[i].R2){p2++;cnt2[A[p2]]++;now+=cnt1[A[p2]];}
while(p1>Q[i].R1){cnt1[A[p1]]--;now-=cnt2[A[p1]];p1--;}
while(p2>Q[i].R2){cnt2[A[p2]]--;now-=cnt1[A[p2]];p2--;}
while(p1<Q[i].R1){p1++;cnt1[A[p1]]++;now+=cnt2[A[p1]];}
ans[Q[i].id]+=now*Q[i].f;
}
for(int i=1;i<=q;i++)
printf("%lld\n",ans[i]);
return 0;
}