「hdu4010」Query on The Trees

2014年12月11日5,39117

Problem Description

We have met so many problems on the tree, so today we will have a query problem on a set of trees.
There are N nodes, each node will have a unique weight Wi. We will have four kinds of operations on it and you should solve them efficiently. Wish you have fun!

Input

There are multiple test cases in our dataset.
For each case, the first line contains only one integer N.(1 ≤ N ≤ 300000) The next N‐1 lines each contains two integers x, y which means there is an edge between them. It also means we will give you one tree initially.
The next line will contains N integers which means the weight Wi of each node. (0 ≤ Wi ≤ 3000)
The next line will contains an integer Q. (1 ≤ Q ≤ 300000) The next Q lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1. Given two integer x, y, you should make a new edge between these two node x and y. So after this operation, two trees will be connected to a new one.
2. Given two integer x, y, you should find the tree in the tree set who contain node x, and you should make the node x be the root of this tree, and then you should cut the edge between node y and its parent. So after this operation, a tree will be separate into two parts.
3. Given three integer w, x, y, for the x, y and all nodes between the path from x to y, you should increase their weight by w.
4. Given two integer x, y, you should check the node weights on the path between x and y, and you should output the maximum weight on it.

Output

For each query you should output the correct answer of it. If you find this query is an illegal operation, you should output ‐1.
You should output a blank line after each test case.

Sample Input

5 1 2 2 4 2 5 1 3 1 2 3 4 5 6 4 2 3 2 1 2 4 2 3 1 3 5 3 2 1 4 4 1 4

Sample Output

3 -1 7

Hint

We define the illegal situation of different operations: In first operation: if node x and y belong to a same tree, we think it’s illegal. In second operation: if x = y or x and y not belong to a same tree, we think it’s illegal. In third operation: if x and y not belong to a same tree, we think it’s illegal. In fourth operation: if x and y not belong to a same tree, we think it’s illegal.

题解

LCT裸题。。。

再不复习很多东西就白学了TAT

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long 
#define inf 2000000000
#define mod 1000000007
#define N 300005
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,top,cnt;
int c[N][2];
int mx[N],fa[N],v[N],tag[N];
int q[N],a[N],b[N],last[N];
bool rev[N];
struct edge{int to,next;}e[N<<1];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void update(int x)
{
    int l=c[x][0],r=c[x][1];
    mx[x]=max(mx[l],mx[r]);
    mx[x]=max(mx[x],v[x]);
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
    if(rev[x])
    {
        rev[l]^=1;rev[r]^=1;rev[x]^=1;
        swap(c[x][0],c[x][1]);
    }
    if(tag[x])
    {
        if(l){tag[l]+=tag[x];mx[l]+=tag[x];v[l]+=tag[x];}
        if(r){tag[r]+=tag[x];mx[r]+=tag[x];v[r]+=tag[x];}
        tag[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[c[y][0]]=0;update(y);
}
int find(int x)
{
    access(x);splay(x);
    while(c[x][0])x=c[x][0];
    return x;
}
void add(int x,int y,int val)
{
    makeroot(x);access(y);splay(y);
	tag[y]+=val;mx[y]+=val;v[y]+=val;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
            last[i]=tag[i]=rev[i]=fa[i]=c[i][0]=c[i][1]=0;
        mx[0]=-inf;cnt=0;
        for(int i=1;i<n;i++)
        {
            int u=read(),v=read();
            insert(u,v);
        }
        for(int i=1;i<=n;i++)mx[i]=v[i]=read();
        q[++top]=1;
        for(int k=1;k<=top;k++)
        {
            int now=q[k];
            for(int i=last[now];i;i=e[i].next)
                if(e[i].to!=fa[now])
                {
                    fa[e[i].to]=now;
                    q[++top]=e[i].to;
                }
        }
        m=read();
        while(m--)
        {
            int opt=read(),x=read(),y=read(),w;
            switch(opt)
            {
            case 1:
                if(find(x)==find(y)){puts("-1");break;}
                link(x,y);break;
            case 2:
                if(find(x)!=find(y)||x==y){puts("-1");break;}
				cut(x,y);
                break;
            case 3:
				w=x;x=y;y=read();
				if(find(x)!=find(y)){puts("-1");break;}
                add(x,y,w);break;
            case 4:
                if(find(x)!=find(y)){puts("-1");break;}
                makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);break;
            }
        }
		puts("");
    }
    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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 2000000000

#define mod 1000000007

#define N 300005

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

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

return x;

}

int n,m,top,cnt;

int c[N][2];

int mx[N],fa[N],v[N],tag[N];

int q[N],a[N],b[N],last[N];

bool rev[N];

struct edge{int to,next;}e[N<<1];

void insert(int u,int v)

{

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

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

}

void update(int x)

{

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

mx[x]=max(mx[l],mx[r]);

mx[x]=max(mx[x],v[x]);

}

void pushdown(int x)

{

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

if(rev[x])

{

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

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

}

if(tag[x])

{

if(l){tag[l]+=tag[x];mx[l]+=tag[x];v[l]+=tag[x];}

if(r){tag[r]+=tag[x];mx[r]+=tag[x];v[r]+=tag[x];}

tag[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[c[y][0]]=0;update(y);

}

int find(int x)

{

access(x);splay(x);

while(c[x][0])x=c[x][0];

return x;

}

void add(int x,int y,int val)

{

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

tag[y]+=val;mx[y]+=val;v[y]+=val;

}

int main()

{

while(scanf("%d",&n)!=EOF)

{

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

last[i]=tag[i]=rev[i]=fa[i]=c[i][0]=c[i][1]=0;

mx[0]=-inf;cnt=0;

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

{

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

insert(u,v);

}

for(int i=1;i<=n;i++)mx[i]=v[i]=read();

q[++top]=1;

for(int k=1;k<=top;k++)

{

int now=q[k];

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

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

{

fa[e[i].to]=now;

q[++top]=e[i].to;

}

m=read();

while(m--)

{

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

switch(opt)

{

case 1:

if(find(x)==find(y)){puts("-1");break;}

link(x,y);break;

case 2:

if(find(x)!=find(y)||x==y){puts("-1");break;}

cut(x,y);

break;

case 3:

w=x;x=y;y=read();

if(find(x)!=find(y)){puts("-1");break;}

add(x,y,w);break;

case 4:

if(find(x)!=find(y)){puts("-1");break;}

makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);break;

}

puts("");

}

return 0;

}

« 「BZOJ2555」SubString 「hdu5002」Tree »

ssqqq

黄学长,这个rev数组是用来干嘛的？窝刚学lct..

hzwer

就是把链的方向反转一下

ssqqq

那么这个也是懒惰标记咯？即不访问不翻转，访问即下传翻转？

然而我看不懂splay。。怎么办

你是不是在常州一中训练过

是

您是？

splay还写左旋右旋的我看完黄学长的代码觉得我弱爆了

syk_____

cut之前为什么要makeroot一次啊感觉可以不用的

尹一航

为什么觉得这个link好奇怪，怎么不用维护y节点的信息呢？

李雪欣

y的fa是x不代表y和x在一个链，这个fa是所谓的path_parent

尹一航

orz

魔法炮

李雪欣？

李雪欣

哈哈哈哈哈哈哈哈

吴一凡

羡慕名字有妹子给起的现充…

魔法炮

233333

魔法炮

一看就是GhobiruKKuribohG神犇又在卖萌

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

「hdu4010」Query on The Trees

分类目录

热门文章

Myfriends

近期评论