「POJ3237」Tree

2014年12月21日6,0120

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

`CHANGE` i v	Change the weight of the ith edge to v
`NEGATE` a b	Negate the weight of every edge on the path from a to b
`QUERY` a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, band c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

Sample Output

1
3

题解

边权放到点权上，树链剖分裸题

negate是mx=-mn mn=-mx

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int bin[15];
int T,n,cnt,P;
int last[10005];
int bl[10005],pos[10005],to[10005];
int fa[10005][14],size[10005],deep[10005];
struct edge{
	int to,next,v;
}e[20005];
struct seg{
	int l,r,mn,mx,tag;
}t[40005];
void solve(int &x,int &y)
{
	int t=x;x=-y;y=-t;
}
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void update(int k)
{
	t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
	t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
void pushdown(int k)
{
	int l=t[k].l,r=t[k].r;
	if(l==r||!t[k].tag)return;t[k].tag=0;
	t[k<<1].tag^=1;t[k<<1|1].tag^=1;
    solve(t[k<<1].mn,t[k<<1].mx);
	solve(t[k<<1|1].mn,t[k<<1|1].mx);
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].tag=0;
	t[k].mn=inf;t[k].mx=-inf;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void change(int k,int x,int val)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==r)
	{
		t[k].mn=t[k].mx=val;return;
	}
	if(x<=mid)change(k<<1,x,val);
	else change(k<<1|1,x,val);
	update(k);
}
void rever(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==x&&r==y)
	{
	    solve(t[k].mn,t[k].mx);
		t[k].tag=1;return;
	}
	if(y<=mid)rever(k<<1,x,y);
	else if(x>mid)rever(k<<1|1,x,y);
	else rever(k<<1,x,mid), rever(k<<1|1,mid+1,y);
	update(k);
}
int query(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(x==l&&y==r)return t[k].mx;
	if(y<=mid)return query(k<<1,x,y);
	else if(x>mid)return query(k<<1|1,x,y);
	else return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
void dfs1(int x)
{
	size[x]=1;
	for(int i=1;i<=13;i++)
		if(bin[i]<=deep[x])
			fa[x][i]=fa[fa[x][i-1]][i-1];
		else break;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x][0])
		{
			deep[e[i].to]=deep[x]+1;
			fa[e[i].to][0]=x;
			dfs1(e[i].to);
			size[x]+=size[e[i].to];
		}
}
void dfs2(int x,int chain)
{
	bl[x]=chain;pos[x]=++P;
	int k=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x][0])
		{
			if(size[e[i].to]>size[k])k=e[i].to;
		}
		else 
		{
			to[i>>1]=pos[x];change(1,pos[x],e[i].v);
		}
	if(!k)return;
	dfs2(k,chain);
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x][0]&&e[i].to!=k)
			dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	for(int i=0;i<=13;i++)
		if(t&bin[i])x=fa[x][i];
	for(int i=13;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	if(x==y)return x;
	return fa[x][0];
}
int solvequery(int x,int f)
{
	int mx=-inf;
	while(bl[x]!=bl[f])
	{
		mx=max(mx,query(1,pos[bl[x]],pos[x]));
		x=fa[bl[x]][0];
	}
	if(pos[f]+1<=pos[x])
		mx=max(mx,query(1,pos[f]+1,pos[x]));
	return mx;
}
void solverever(int x,int f)
{
	while(bl[x]!=bl[f])
	{
		rever(1,pos[bl[x]],pos[x]);
		x=fa[bl[x]][0];
	}
	if(pos[f]+1<=pos[x])
		rever(1,pos[f]+1,pos[x]);
}
int main()
{
	bin[0]=1;for(int i=1;i<15;i++)bin[i]=bin[i-1]<<1;
	T=read();
	while(T--)
	{
		P=0;cnt=1;
		memset(last,0,sizeof(last));
		memset(deep,0,sizeof(deep));
		memset(fa,0,sizeof(fa));
		n=read();
		for(int i=1;i<n;i++)
		{
			int u=read(),v=read(),w=read();
			insert(u,v,w);
		}
		build(1,1,n);
		dfs1(1);
		dfs2(1,1);
		char ch[10];
		while(scanf("%s",ch+1))
		{
			if(ch[1]=='D')break;
			int x=read(),y=read();
			if(ch[1]=='Q')
			{
				int f=lca(x,y);
				printf("%d\n",max(solvequery(x,f),solvequery(y,f)));
			}
			if(ch[1]=='C')
				change(1,to[x],y);
			if(ch[1]=='N')
			{
				int f=lca(x,y);
				solverever(x,f);solverever(y,f);
			}
		}
	}
	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

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[15];

int T,n,cnt,P;

int last[10005];

int bl[10005],pos[10005],to[10005];

int fa[10005][14],size[10005],deep[10005];

struct edge{

int to,next,v;

}e[20005];

struct seg{

int l,r,mn,mx,tag;

}t[40005];

void solve(int &x,int &y)

{

int t=x;x=-y;y=-t;

}

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void update(int k)

{

t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);

t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);

}

void pushdown(int k)

{

int l=t[k].l,r=t[k].r;

if(l==r||!t[k].tag)return;t[k].tag=0;

t[k<<1].tag^=1;t[k<<1|1].tag^=1;

solve(t[k<<1].mn,t[k<<1].mx);

solve(t[k<<1|1].mn,t[k<<1|1].mx);

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;t[k].tag=0;

t[k].mn=inf;t[k].mx=-inf;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void change(int k,int x,int val)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==r)

{

t[k].mn=t[k].mx=val;return;

}

if(x<=mid)change(k<<1,x,val);

else change(k<<1|1,x,val);

update(k);

}

void rever(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==x&&r==y)

{

solve(t[k].mn,t[k].mx);

t[k].tag=1;return;

}

if(y<=mid)rever(k<<1,x,y);

else if(x>mid)rever(k<<1|1,x,y);

else rever(k<<1,x,mid), rever(k<<1|1,mid+1,y);

update(k);

}

int query(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(x==l&&y==r)return t[k].mx;

if(y<=mid)return query(k<<1,x,y);

else if(x>mid)return query(k<<1|1,x,y);

else return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y));

}

void dfs1(int x)

{

size[x]=1;

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

if(bin[i]<=deep[x])

fa[x][i]=fa[fa[x][i-1]][i-1];

else break;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0])

{

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

dfs1(e[i].to);

size[x]+=size[e[i].to];

}

void dfs2(int x,int chain)

{

bl[x]=chain;pos[x]=++P;

int k=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0])

{

if(size[e[i].to]>size[k])k=e[i].to;

}

else

{

to[i>>1]=pos[x];change(1,pos[x],e[i].v);

}

if(!k)return;

dfs2(k,chain);

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=13;i++)

if(t&bin[i])x=fa[x][i];

for(int i=13;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

int solvequery(int x,int f)

{

int mx=-inf;

while(bl[x]!=bl[f])

{

mx=max(mx,query(1,pos[bl[x]],pos[x]));

x=fa[bl[x]][0];

}

if(pos[f]+1<=pos[x])

mx=max(mx,query(1,pos[f]+1,pos[x]));

return mx;

}

void solverever(int x,int f)

{

while(bl[x]!=bl[f])

{

rever(1,pos[bl[x]],pos[x]);

x=fa[bl[x]][0];

}

if(pos[f]+1<=pos[x])

rever(1,pos[f]+1,pos[x]);

}

int main()

{

bin[0]=1;for(int i=1;i<15;i++)bin[i]=bin[i-1]<<1;

T=read();

while(T--)

{

P=0;cnt=1;

memset(last,0,sizeof(last));

memset(deep,0,sizeof(deep));

memset(fa,0,sizeof(fa));

n=read();

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

{

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

insert(u,v,w);

}

build(1,1,n);

dfs1(1);

dfs2(1,1);

char ch[10];

while(scanf("%s",ch+1))

{

if(ch[1]=='D')break;

int x=read(),y=read();

if(ch[1]=='Q')

{

int f=lca(x,y);

printf("%d\n",max(solvequery(x,f),solvequery(y,f)));

}

if(ch[1]=='C')

change(1,to[x],y);

if(ch[1]=='N')

{

int f=lca(x,y);

solverever(x,f);solverever(y,f);

}

return 0;

}

« 「BZOJ3747」[POI2015] Kinoman 「CF498D」Traffic Jams in the Land »

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

「POJ3237」Tree

分类目录

热门文章

Myfriends

近期评论