「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;
}