HDOJ 4010 Query on The Trees LCT
2024-08-29 10:34:42
LCT:
分割、合并子树,路径上全部点的点权添加一个值,查询路径上点权的最大值
Query on The Trees
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 2582 Accepted Submission(s): 1208
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!
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.
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.
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
7HintWe 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.
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn=330000; int ch[maxn][2],pre[maxn],key[maxn];
int add[maxn],rev[maxn],Max[maxn];
bool rt[maxn]; void update_add(int r,int d)
{
if(!r) return ;
key[r]+=d;
add[r]+=d;
Max[r]+=d;
} void update_rev(int r)
{
if(!r) return ;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
} void push_down(int r)
{
if(add[r])
{
update_add(ch[r][0],add[r]);
update_add(ch[r][1],add[r]);
add[r]=0;
}
if(rev[r])
{
update_rev(ch[r][0]);
update_rev(ch[r][1]);
rev[r]=0;
}
} void push_up(int r)
{
Max[r]=max(max(Max[ch[r][0]],Max[ch[r][1]]),key[r]);
} void Rotate(int x)
{
int y=pre[x],kind=(ch[y][1]==x);
ch[y][kind]=ch[x][!kind];
pre[ch[y][kind]]=y;
pre[x]=pre[y];
pre[y]=x;
ch[x][!kind]=y;
if(rt[y]) rt[y]=false,rt[x]=true;
else ch[pre[x]][ch[pre[x]][1]==y]=x;
push_up(y);
} void P(int r)
{
if(!rt[r]) P(pre[r]);
push_down(r);
} void Splay(int r)
{
P(r);
while(!rt[r])
{
int f=pre[r],ff=pre[f];
if(rt[f]) Rotate(r);
else if((ch[ff][1]==f)==(ch[f][1]==r)) Rotate(f),Rotate(r);
else Rotate(r),Rotate(r);
}
push_up(r);
} int Access(int x)
{
int y=0;
for(;x;x=pre[y=x])
{
Splay(x);
rt[ch[x][1]]=true; rt[ch[x][1]=y]=false;
push_up(x);
}
return y;
} bool judge(int u,int v)
{
while(pre[u]) u=pre[u];
while(pre[v]) v=pre[v];
return u==v;
} void mroot(int r)
{
Access(r);
Splay(r);
update_rev(r);
} void lca(int &u,int &v)
{
Access(v); v=0;
while(u)
{
Splay(u);
if(!pre[u]) return ;
rt[ch[u][1]]=true;
rt[ch[u][1]=v]=false;
push_up(u);
u=pre[v=u];
}
} void link(int u,int v)
{
if(judge(u,v))
{
puts("-1");
return ;
}
mroot(u);
pre[u]=v;
} void cut(int u,int v)
{
if(u==v||!judge(u,v))
{
puts("-1");
return ;
}
mroot(u);
Splay(v);
pre[ch[v][0]]=pre[v];
pre[v]=0;
rt[ch[v][0]]=true;
ch[v][0]=0;
push_up(v);
} void Add(int u,int v,int w)
{
if(!judge(u,v))
{
puts("-1"); return ;
}
lca(u,v);
update_add(ch[u][1],w);
update_add(v,w);
key[u]+=w;
push_up(u);
} void query(int u,int v)
{
if(!judge(u,v))
{
puts("-1");
return ;
}
lca(u,v);
printf("%d\n",max(max(Max[v],Max[ch[u][1]]),key[u]));
} struct Edge
{
int to,next;
}edge[maxn*2]; int Adj[maxn],Size=0; void init()
{
memset(Adj,-1,sizeof(Adj)); Size=0;
} void add_edge(int u,int v)
{
edge[Size].to=v;
edge[Size].next=Adj[u];
Adj[u]=Size++;
} void dfs(int u)
{
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(pre[v]!=0) continue;
pre[v]=u;
dfs(v);
}
}
int n; int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=0;i<n+10;i++)
{
pre[i]=0; ch[i][0]=ch[i][1]=0;
rev[i]=0; add[i]=0; rt[i]=true;
} for(int i=0;i<n-1;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
pre[1]=-1; dfs(1); pre[1]=0; for(int i=1;i<=n;i++)
{
scanf("%d",key+i);
Max[i]=key[i];
} int q;
scanf("%d",&q);
while(q--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y;
scanf("%d%d",&x,&y);
link(x,y);
}
else if(op==2)
{
int x,y;
scanf("%d%d",&x,&y);
cut(x,y);
}
else if(op==3)
{
int x,y,w;
scanf("%d%d%d",&w,&x,&y);
Add(x,y,w);
}
else if(op==4)
{
int x,y;
scanf("%d%d",&x,&y);
query(x,y);
}
}
putchar(10);
}
return 0;
}
最新文章
- DuiLib 源码分析之解析xml类CMarkup &; CMarkupNode cpp文件
- BZOJ2683 简单题(CDQ分治)
- 国外HTML网站模版(卖成品模版)
- js和jQuery 获取屏幕高度、宽度
- Android性能调优
- 两个div之间有空隙
- Break和Continue的一些注意事项
- C#Equal的使用
- Web服务器和动态语言如何交互--CGI&;FastCGI&;FPM浅谈
- XML文件解析之--DOM与SAX
- MapReduce-TextInputFormat 切片机制
- 爬虫系列之mongodb
- 用PHPExcel导出导入Excel
- Postman A请求的返回值作为B请求的入参( 之‘’token‘’ ,用代码设置全局变量)
- c语言: 修改参数的地址,及注意事项
- 机器学习-树模型理论(GDBT,xgboost,lightBoost,随机森林)
- 剥开比原看代码12:比原是如何通过/create-account-receiver创建地址的?
- ThinkPHP框架学习(一)
- Nginx+Tomcat+Memcached 实现集群部署时Session共享
- Java并发编程:volatile关键字解析<;转>;