「BZOJ2631」tree

2014年8月8日7,91311

Description

　一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c；
– u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。

Input

　　第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作

Output

　　对于每个/对应的答案输出一行

Sample Input

3 2
1 2
2 3
* 1 3 4
/ 1 1

Sample Output

HINT

数据规模和约定
10%的数据保证，1<=n，q<=2000
另外15%的数据保证，1<=n，q<=5*10^4，没有-操作，并且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4，没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4

题解

其实这题不需要开long long。。。只要unsigned int，不然可能会T

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define mod 51061
#define ll unsigned int
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;
}
int n,m,top,cnt;
int c[100005][2],fa[100005];
int size[100005],q[100005];
bool rev[100005];
ll sum[100005],val[100005],at[100005],mt[100005];
void cal(int x,int m,int a)
{
	if(!x)return;
	val[x]=(val[x]*m+a)%mod;
	sum[x]=(sum[x]*m+a*size[x])%mod;
	at[x]=(at[x]*m+a)%mod;
	mt[x]=(mt[x]*m)%mod;
}
bool isroot(int x)
{
	return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	sum[x]=(sum[l]+sum[r]+val[x])%mod;
	size[x]=(size[l]+size[r]+1)%mod;
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(rev[x])
	{
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
	int m=mt[x],a=at[x];
	mt[x]=1;at[x]=0;
	if(m!=1||a!=0)
	{
		cal(l,m,a);cal(r,m,a);
	}
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l,r;
	l=(c[y][1]==x);r=l^1;
	if(!isroot(y))c[z][c[z][1]==y]=x;
	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x)
{
	q[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])
		q[++top]=fa[i];
	while(top)pushdown(q[top--]);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	for(int t=0;x;t=x,x=fa[x])
	{
		splay(x);c[x][1]=t;update(x);
	}
}
void makeroot(int x)
{
	access(x);splay(x);rev[x]^=1;
}
void split(int x,int y)
{
	makeroot(y);access(x);splay(x);
}
void link(int x,int y)
{
	makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;
}
int main()
{
	n=read();m=read();
	int u,v,c;
	for(int i=1;i<=n;i++)
		val[i]=sum[i]=mt[i]=size[i]=1;
	for(int i=1;i<n;i++)
	{
		u=read(),v=read();
		link(u,v);
	}
	char ch[5];
	while(m--)
	{
		scanf("%s",ch);
		u=read();v=read();
		if(ch[0]=='+')
		{
			c=read();
			split(u,v);cal(u,1,c);
		}
		if(ch[0]=='-')
		{
			cut(u,v);
			u=read();v=read();link(u,v);
		}
		if(ch[0]=='*')
		{
			c=read();
			split(u,v);cal(u,c,0);
		}
		if(ch[0]=='/')
		{
			split(u,v);
			printf("%d\n",sum[u]);
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<complex>

#include<iostream>

#include<algorithm>

#define mod 51061

#define ll unsigned int

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;

}

int n,m,top,cnt;

int c[100005][2],fa[100005];

int size[100005],q[100005];

bool rev[100005];

ll sum[100005],val[100005],at[100005],mt[100005];

void cal(int x,int m,int a)

{

if(!x)return;

val[x]=(val[x]*m+a)%mod;

sum[x]=(sum[x]*m+a*size[x])%mod;

at[x]=(at[x]*m+a)%mod;

mt[x]=(mt[x]*m)%mod;

}

bool isroot(int x)

{

return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;

}

void update(int x)

{

int l=c[x][0],r=c[x][1];

sum[x]=(sum[l]+sum[r]+val[x])%mod;

size[x]=(size[l]+size[r]+1)%mod;

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

if(rev[x])

{

rev[x]^=1;rev[l]^=1;rev[r]^=1;

swap(c[x][0],c[x][1]);

}

int m=mt[x],a=at[x];

mt[x]=1;at[x]=0;

if(m!=1||a!=0)

{

cal(l,m,a);cal(r,m,a);

}

void rotate(int x)

{

int y=fa[x],z=fa[y],l,r;

l=(c[y][1]==x);r=l^1;

if(!isroot(y))c[z][c[z][1]==y]=x;

fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x)

{

q[++top]=x;

for(int i=x;!isroot(i);i=fa[i])

q[++top]=fa[i];

while(top)pushdown(q[top--]);

while(!isroot(x))

{

int y=fa[x],z=fa[y];

if(!isroot(y))

{

if(c[y][0]==x^c[z][0]==y)rotate(x);

else rotate(y);

}

rotate(x);

}

void access(int x)

{

for(int t=0;x;t=x,x=fa[x])

{

splay(x);c[x][1]=t;update(x);

}

void makeroot(int x)

{

access(x);splay(x);rev[x]^=1;

}

void split(int x,int y)

{

makeroot(y);access(x);splay(x);

}

void link(int x,int y)

{

makeroot(x);fa[x]=y;

}

void cut(int x,int y)

{

makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;

}

int main()

{

n=read();m=read();

int u,v,c;

for(int i=1;i<=n;i++)

val[i]=sum[i]=mt[i]=size[i]=1;

for(int i=1;i<n;i++)

{

u=read(),v=read();

link(u,v);

}

char ch[5];

while(m--)

{

scanf("%s",ch);

u=read();v=read();

if(ch[0]=='+')

{

c=read();

split(u,v);cal(u,1,c);

}

if(ch[0]=='-')

{

cut(u,v);

u=read();v=read();link(u,v);

}

if(ch[0]=='*')

{

c=read();

split(u,v);cal(u,c,0);

}

if(ch[0]=='/')

{

split(u,v);

printf("%d\n",sum[u]);

}

return 0;

}

« 「BZOJ2002」[HNOI2010] Bounce 弹飞绵羊 NOI2014魔法森林 »

李天逸

黄学长，请问cut的时候为什么不需要update?

小蒟蒻

黄学长，请问isroot()能不能这样判断：
bool isroot(int x) { return fa[ x ] > 0; }

hzwer

不可以，lct维护的一堆splay中，只有1棵splay的根是0，其余的根指向上一条重边。
还有你说的有根树不会有什么问题吧。

小蒟蒻

可是您打了一个rev标记，那就是说每次makeroot()之后节点相对深度都会改变，根节点不会随之变化吗？

小蒟蒻

黄学长，请问您写的LCT如何处理有根树的问题？

6 1
1 2
2 3
3 4
1 5
4 6
/ 4 5
这组数据好像不大对啊0.0,为什么输出了3？（好像是5）

hzwer

已更正

涵丶

为什么这个地方不用dfs而是一个一个link就行？

hzwer

随意QAQ

吴钰晗

“其实这题不需要开long long。。。只要unsigned int，不然可能会T”是可怕

HugeG

hzwer.com _ Home | http://hzwer.com

「BZOJ2631」tree

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论