「hdu5002」Tree

2014年12月13日3,8080

Problem Description

You are given a tree with N nodes which are numbered by integers 1..N. Each node is associated with an integer as the weight.

Your task is to deal with M operations of 4 types:

1.Delete an edge (x, y) from the tree, and then add a new edge (a, b). We ensure that it still constitutes a tree after adding the new edge.

2.Given two nodes a and b in the tree, change the weights of all the nodes on the path connecting node a and b (including node a and b) to a particular value x.

3.Given two nodes a and b in the tree, increase the weights of all the nodes on the path connecting node a and b (including node a and b) by a particular value d.

4.Given two nodes a and b in the tree, compute the second largest weight on the path connecting node a and b (including node a and b), and the number of times this weight occurs on the path. Note that here we need the strict second largest weight. For instance, the strict second largest weight of {3, 5, 2, 5, 3} is 3.

Input

The first line contains an integer T (T<=3), which means there are T test cases in the input.

For each test case, the first line contains two integers N and M (N, M<=10^5). The second line contains N integers, and the i-th integer is the weight of the i-th node in the tree (their absolute values are not larger than 10^4).

In next N-1 lines, there are two integers a and b (1<=a, b<=N), which means there exists an edge connecting node a and b.

The next M lines describe the operations you have to deal with. In each line the first integer is c (1<=c<=4), which indicates the type of operation.

If c = 1, there are four integers x, y, a, b (1<= x, y, a, b <=N) after c.
If c = 2, there are three integers a, b, x (1<= a, b<=N, |x|<=10^4) after c.
If c = 3, there are three integers a, b, d (1<= a, b<=N, |d|<=10^4) after c.
If c = 4 (it is a query operation), there are two integers a, b (1<= a, b<=N) after c.

All these parameters have the same meaning as described in problem description.

Output

For each test case, first output “Case #x:”” (x means case ID) in a separate line.

For each query operation, output two values: the second largest weight and the number of times it occurs. If the weights of nodes on that path are all the same, just output “ALL SAME” (without quotes).

Sample Input

2 3 2 1 1 2 1 2 1 3 4 1 2 4 2 3 7 7 5 3 2 1 7 3 6 1 2 1 3 3 4 3 5 4 6 4 7 4 2 6 3 4 5 -1 4 5 7 1 3 4 2 4 4 3 6 2 3 6 5 4 3 6

Sample Output

Case #1: ALL SAME 1 2 Case #2: 3 2 1 1 3 2 ALL SAME

题解

1：删边加边

2：路径修改

3：路径加

4：询问路径次大值及其个数

为了实现4操作，对每个节点维护最大值与次大值及个数，记为mx1,mx2,c1,c2，设x的值为v

比如往节点x加入c个值为val的数，用 solve(x,val,c) 处理

则应分四种情况维护x的信息

if(val>mx1[x])mx2[x]=mx1[x],mx1[x]=val,c2[x]=c1[x],c1[x]=c;
else if(val==mx1[x])c1[x]+=c;
else if(val>mx2[x])mx2[x]=val,c2[x]=c;
else if(val==mx2[x])c2[x]+=c;

设其左右儿子为l，r在update时只需要

清空x的信息

solve(x,v[x],1);
solve(x,mx1[l],c1[l]),solve(x,mx2[l],c2[l]);
solve(x,mx1[r],c1[r]),solve(x,mx2[r],c2[r]);

这样写应该会比较清楚

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define inf 2000000000
#define ll long long 
#define N 100005
using namespace std;
inline 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 T;
int n,m,top;
int q[N];
int c[N][2],fa[N],v[N];
int mx1[N],mx2[N],c1[N],c2[N],size[N];
int ta[N],tc[N];
bool rev[N];
void solve(int x,int val,int c)
{
	if(val>mx1[x])mx2[x]=mx1[x],mx1[x]=val,c2[x]=c1[x],c1[x]=c;
	else if(val==mx1[x])c1[x]+=c;
	else if(val>mx2[x])mx2[x]=val,c2[x]=c;
	else if(val==mx2[x])c2[x]+=c;
}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	mx1[x]=mx2[x]=-inf;c1[x]=c2[x]=0;
    solve(x,v[x],1);
	if(l)solve(x,mx1[l],c1[l]),solve(x,mx2[l],c2[l]);
	if(r)solve(x,mx1[r],c1[r]),solve(x,mx2[r],c2[r]);
	size[x]=size[l]+size[r]+1;
}
void add(int y,int val)
{
	mx1[y]+=val;v[y]+=val;
	if(mx2[y]!=-inf)mx2[y]+=val;
	ta[y]+=val;
}
void change(int y,int val)
{
	mx1[y]=val;v[y]=val;c1[y]=size[y];
	mx2[y]=-inf;c2[y]=0;
    tc[y]=val;
	if(ta[y])ta[y]=0;
}
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]);
	}
	if(tc[x]!=-inf)
	{
		if(l)change(l,tc[x]);
		if(r)change(r,tc[x]);
		tc[x]=-inf;
	}
	if(ta[x])
	{
		if(l)add(l,ta[x]);
		if(r)add(r,ta[x]);
		ta[x]=0;
	}
}
bool isroot(int x)
{
	return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l,r;
	if(c[y][0]==x)l=0;else l=1;r=l^1;
	if(!isroot(y))
	{
		if(c[z][0]==y)c[z][0]=x;else c[z][1]=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)
{
	top=0;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 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;update(y);
}
void query(int x,int y)
{
   makeroot(x);access(y);splay(y);
	if(c1[y]==size[y])puts("ALL SAME");
	else printf("%d %d\n",mx2[y],c2[y]);
}
int main()
{
	T=read();
	for(int cas=1;cas<=T;cas++)
	{
		printf("Case #%d:\n",cas);
		n=read();m=read();
		for(int i=1;i<=n;i++)
			v[i]=read();
		for(int i=1;i<=n;i++)
		{
			mx1[i]=v[i],c1[i]=1;
			mx2[i]=-inf,c2[i]=0;
			size[i]=1;
		}
		for(int i=1;i<=n;i++)
		{
			fa[i]=c[i][0]=c[i][1]=0;
			ta[i]=rev[i]=0;tc[i]=-inf;
		}
		for(int i=1;i<n;i++)
		{
			int u=read(),v=read();
			link(u,v);
		}
		int opt,x,y,a,b,d;
	    while(m--)
		{
		    opt=read();
			if(opt==1)
			{
				x=read();y=read();a=read();b=read();
				cut(x,y);link(a,b);
			}
			else if(opt==2)
			{
				a=read();b=read();x=read();
				makeroot(a);access(b);splay(b);
				change(b,x);
			}
			else if(opt==3)
			{
				a=read();b=read();d=read();
				makeroot(a);access(b);splay(b);
				add(b,d);
			}
			else 
			{
				a=read();b=read();
				query(a,b);
			}
		}
	}
	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

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#define inf 2000000000

#define ll long long

#define N 100005

using namespace std;

inline 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 T;

int n,m,top;

int q[N];

int c[N][2],fa[N],v[N];

int mx1[N],mx2[N],c1[N],c2[N],size[N];

int ta[N],tc[N];

bool rev[N];

void solve(int x,int val,int c)

{

if(val>mx1[x])mx2[x]=mx1[x],mx1[x]=val,c2[x]=c1[x],c1[x]=c;

else if(val==mx1[x])c1[x]+=c;

else if(val>mx2[x])mx2[x]=val,c2[x]=c;

else if(val==mx2[x])c2[x]+=c;

}

void update(int x)

{

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

mx1[x]=mx2[x]=-inf;c1[x]=c2[x]=0;

solve(x,v[x],1);

if(l)solve(x,mx1[l],c1[l]),solve(x,mx2[l],c2[l]);

if(r)solve(x,mx1[r],c1[r]),solve(x,mx2[r],c2[r]);

size[x]=size[l]+size[r]+1;

}

void add(int y,int val)

{

mx1[y]+=val;v[y]+=val;

if(mx2[y]!=-inf)mx2[y]+=val;

ta[y]+=val;

}

void change(int y,int val)

{

mx1[y]=val;v[y]=val;c1[y]=size[y];

mx2[y]=-inf;c2[y]=0;

tc[y]=val;

if(ta[y])ta[y]=0;

}

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]);

}

if(tc[x]!=-inf)

{

if(l)change(l,tc[x]);

if(r)change(r,tc[x]);

tc[x]=-inf;

}

if(ta[x])

{

if(l)add(l,ta[x]);

if(r)add(r,ta[x]);

ta[x]=0;

}

bool isroot(int x)

{

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

}

void rotate(int x)

{

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

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

if(!isroot(y))

{

if(c[z][0]==y)c[z][0]=x;else c[z][1]=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)

{

top=0;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 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;update(y);

}

void query(int x,int y)

{

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

if(c1[y]==size[y])puts("ALL SAME");

else printf("%d %d\n",mx2[y],c2[y]);

}

int main()

{

T=read();

for(int cas=1;cas<=T;cas++)

{

printf("Case #%d:\n",cas);

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

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

v[i]=read();

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

{

mx1[i]=v[i],c1[i]=1;

mx2[i]=-inf,c2[i]=0;

size[i]=1;

}

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

{

fa[i]=c[i][0]=c[i][1]=0;

ta[i]=rev[i]=0;tc[i]=-inf;

}

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

{

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

link(u,v);

}

int opt,x,y,a,b,d;

while(m--)

{

opt=read();

if(opt==1)

{

x=read();y=read();a=read();b=read();

cut(x,y);link(a,b);

}

else if(opt==2)

{

a=read();b=read();x=read();

makeroot(a);access(b);splay(b);

change(b,x);

}

else if(opt==3)

{

a=read();b=read();d=read();

makeroot(a);access(b);splay(b);

add(b,d);

}

else

{

a=read();b=read();

query(a,b);

}

return 0;

}

« 「hdu4010」Query on The Trees 「BZOJ2157」旅游 »

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

「hdu5002」Tree

分类目录

热门文章

Myfriends

近期评论