QTREE系列1~7 的 LCT解法

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

早就想把QTREE序列搞完的，一直拖到现在才搞。 使用LCT把QTREE序列都搞了一遍。

先贴个题目链接：

QTREE1 QTREE2 QTREE3 QTREE4 QTREE5 QTREE6 QTREE7 QTREE6和QTREE7是岛娘的经典之作，简直不能更经典。 QTREE1，QTRE2，QTREE3都是比较水的了，搞路径的都比较简单，QTREE4和QTREE5是子树的比较赞。

QTREE1

题意： 给定一棵n个结点的树，树的边上有权。有两种操作： 1.修改一条边上的权值。 2.查询两个结点x和y之间的最短路径中经过的最大的边的权值。 其中\(n<=10^4\) 很水了，LCT直接搞就是了，维护最大值。 有点卡常数，SPOJ太慢了！SPOJ太慢了！SPOJ太慢了！SPOJ太慢了！ 反正代码没怎么优化，有的时候还加了输入挂，各种优化加上去就难看了。

/* ***
Author :kuangbin
Created Time :2014/8/26 17:58:27
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
// http://www.spoj.com/problems/QTREE/
const int MAXN = 10010;
struct Node null;
struct Node{
Node \fa,*ch[2];
int Max,key;
inline void push_up(){
if(this == null)return;
Max = max(key,max(ch[0]->Max,ch[1]->Max));
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot() {
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa,*ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay()->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->Max = null->key = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->fa = node[i]->ch[0] = node[i]->ch[1] = null;
node[i]->Max = node[i]->key = 0;
}
}
struct Edge{
int to,next;
int w,id;
}edge[MAXN2];
int head[MAXN],tot;
inline int addedge(int u,int v,int w,int id){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].id = id;
edge[tot].next = head[u];
head[u] = tot++;
}
Node ee[MAXN];
bool vis[MAXN];
void bfs(int n){
for(int i = 1;i <= n;i++)vis[i] = false;
queueq;
q.push(1);
vis[1] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(vis[v])continue;
vis[v] = true;
q.push(v);
ee[edge[i].id] = node[v];
node[v]->key = edge[i].w;
node[v]->push_up();
node[v]->fa = node[u];
}
}
}
inline int ask(Node *x,Node *y){
x->access();
for(x = null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null)return max(y->ch[1]->Max,x->Max);
y->setc(x,1);
y->push_up();
}
}
int main()
{
int T;
scanf(“%d”,&T);
int n;
while(T–){
scanf(“%d”,&n);
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
init(n);
int u,v,w;
for(int i = 1;i < n;i++){
scanf(“%d%d%d”,&u,&v,&w);
addedge(u,v,w,i);
addedge(v,u,w,i);
}
bfs(n);
char op[20];
int x,y;
while(scanf(“%s”,op) == 1){
if(strcmp(op,”DONE”) == 0)break;
scanf(“%d%d”,&x,&y);
if(op[0] == ‘Q’){
printf(“%d\n”,ask(node[x],node[y]));
}
else {
ee[x]->splay()->key = y;
ee[x]->push_up();
}
}
}
return 0;
}

QTREE2

题意： 给定一棵n个结点的树，树的边上有权。有两种操作： 1.查询两个结点x和y之间的最短路径长度。 2.查询从x到y的最短路径的第K条边的长度。 其中 \(n<=10^4\) 连修改操作都没有，简直随便搞！

/* ***
Author :kuangbin
Created Time :2014/8/26 21:42:19
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE2.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
// http://www.spoj.com/problems/QTREE2/
const int MAXN = 10010;
struct Node null;
struct Node{
Node \fa,*ch[2];
int sum,val;
int size;
int id;
void clear(){
fa = ch[0] = ch[1] = null;
sum = val = 0;
size = 1;
}
inline void push_up(){
if(this == null)return;
sum = val + ch[0]->sum + ch[1]->sum;
size = ch[0]->size + ch[1]->size + 1;
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay()->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->size = null->sum = null->val = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->id = i;
node[i]->clear();
}
}
struct Edge{
int to,next;
int w;
}edge[MAXN2];
int head[MAXN],tot;
inline void addedge(int u,int v,int w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
dfs(v,u);
node[v]->val = edge[i].w;
node[v]->push_up();
node[v]->fa = node[u];
}
}
//查询x->y的距离
inline int query_sum(Node \x,Node *y){
x->access();
for(x = null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null)
return y->ch[1]->sum + x->sum;
y->setc(x,1);
y->push_up();
}
}
//在splay中得到第k个点
Node get_kth(Node r,int k){
Node x = r;
while(x->ch[0]->size+1 != k){
if(k < x->ch[0]->size+1)x = x->ch[0];
else {
k -= x->ch[0]->size+1;
x = x->ch[1];
}
}
return x;
}
//查询x->y路径上的第k个点
inline int query_kth(Node \x,Node *y,int k){
x->access();
for(x = null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null){
if(y->ch[1]->size+1 == k)return y->id;
else if(y->ch[1]->size+1 > k)
return get_kth(y->ch[1],y->ch[1]->size+1-k)->id;
else return get_kth(x,k-(y->ch[1]->size+1))->id;
}
y->setc(x,1);
y->push_up();
}
}
int main()
{
int T,n;
scanf(“%d”,&T);
while(T–){
scanf(“%d”,&n);
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
init(n);
int u,v,w;
for(int i = 1;i < n;i++){
scanf(“%d%d%d”,&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dfs(1,1);
char op[20];
while(scanf(“%s”,op) == 1){
if(strcmp(op,”DONE”) == 0)break;
if(op[0] == ‘D’){
scanf(“%d%d”,&u,&v);
printf(“%d\n”,query_sum(node[u],node[v]));
}
else {
int k; scanf(“%d%d%d”,&u,&v,&k);
printf(“%d\n”,query_kth(node[u],node[v],k));
}
}
}
return 0;
}

QTREE3

题意： 给定一棵n个结点的树，树的每个结点有黑白两色，初始时都是白的。两种操作： 1.对一个结点执行反色操作（白变黑，黑变白） 2.查询从1号结点到i号结点的路径上的第一个黑色结点编号。 其中\(n<=10^5\). 查询数目不超过\(10^5\). LCT维护路径上的白点和黑点数目，然后就可以解决了。 水题！

/* ***
Author :kuangbin
Created Time :2014/8/27 17:34:19
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE3.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
//http://www.spoj.com/problems/QTREE3/
const int MAXN = 100010;
struct Node null;
struct Node{
Node \fa,*ch[2];
int val,sum;
int id;
void clear(){
fa = ch[0] = ch[1] = null;
val = sum = 0;
}
inline void push_up(){
if(this == null)return;
sum = val + ch[0]->sum + ch[1]->sum;
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this ,*q = null; p != null; q = p, p = p->fa){
p->splay()->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->val = null->sum = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->clear();
node[i]->id = i;
}
}
struct Edge{
int to,next;
}edge[MAXN2];
int head[MAXN],tot;
inline void addedge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
dfs(v,u);
node[v]->fa = node[u];
}
}
void change(int u){
node[u]->splay()->val ^= 1;
node[u]->push_up();
}
int ask(int v){
node[v]->access();
node[v]->splay();
if(node[v]->sum == 0)return -1;
Node x = node[v];
while(x != null){
if(x->ch[0]->sum == 0 && x->val == 1)return x->id;
if(x->ch[0]->sum)x = x->ch[0];
else x = x->ch[1];
}
}

int main()
{
int n,m;
while(scanf(“%d%d”,&n,&m) == 2){
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
init(n);
int u,v;
for(int i = 1;i < n;i++){
scanf(“%d%d”,&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(1,1);
while(m–){
scanf(“%d%d”,&u,&v);
if(u == 0)change(v);
else printf(“%d\n”,ask(v));
}
}
return 0;
}

QTREE4

题意： 给定一棵n个结点的树，树的边上有权，每个结点有黑白两色，初始时所有的结点都是白的。有两种操作： 1.对一个结点执行反色操作（白变黑，黑变白） 2.查询树中距离最远的两个白点的距离。 其中\(n<=10^5\)，查询数目不超过\(10^5\). 做法比较多，有树链剖分，树分治等。 LCT搞起来代码比较短。 经典的要子树的操作，每个点要加set,维护虚边的信息。 关键是写push_up()操作。 也是会卡常数。要谨慎。

/* ***
Author :kuangbin
Created Time :2014/8/27 23:29:59
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE4.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
//http://www.spoj.com/problems/QTREE4/
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
struct Node null;
struct Node{
Node \fa,*ch[2];
multisetst0,st1;//st0是链，st1是路径
int dd,d0;//d0是该点对应边的长度，dd是重链长度
int w0;//白点值为0，黑点值为-INF
int ls,rs,ms;
inline void clear(){
fa = ch[0] = ch[1] = null;
st0.clear(); st1.clear();
st0.insert(-INF);
st0.insert(-INF);
st1.insert(-INF);
w0 = 0; dd = d0 = 0;
ls = rs = ms = -INF;
}
inline void push_up(){
if(this == null)return;
dd = d0 + ch[0]->dd + ch[1]->dd;
int m0 = max(w0,st0.rbegin()), ml = max(m0,ch[0]->rs+d0), mr = max(m0,ch[1]->ls);
ls = max(ch[0]->ls,ch[0]->dd + d0 + mr);
rs = max(ch[1]->rs,ch[1]->dd + ml);
multiset::reverse_iterator it = st0.rbegin();
++it;
int t0 = max((\st0.rbegin()) + (*it) , st1.rbegin());
if(w0 == 0)
t0 = max(t0,max(0,st0.rbegin()));
ms = max(max(max(ml+ch[1]->ls,mr+d0+ch[0]->rs),max(ch[0]->ms,ch[1]->ms)),t0);
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay();
if(p->ch[1] != null){
p->st0.insert(p->ch[1]->ls);
p->st1.insert(p->ch[1]->ms);
}
if(q != null){
p->st0.erase(p->st0.find(q->ls));
p->st1.erase(p->st1.find(q->ms));
}
p->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
inline void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->st0.clear(); null->st1.clear();
null->ls = null->rs = null->ms = -INF;
null->w0 = -INF;
null->d0 = null->dd = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->clear();
}
}
struct Edge{
int to,next,w;
}edge[MAXN2];
int head[MAXN],tot;
inline void addedge(int u,int v,int w){
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
inline void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
node[v]->fa = node[u];
node[v]->d0 = edge[i].w;
dfs(v,u);
node[u]->st0.insert(node[v]->ls);
node[u]->st1.insert(node[v]->ms);
}
node[u]->push_up();
}
//适用于正负整数
template
inline bool scan_d(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!=’-‘&&(c<’0’||c>’9’)) c=getchar();
sgn=(c==’-‘)?-1:1;
ret=(c==’-‘)?0:(c-‘0’);
while(c=getchar(),c>=’0’&&c<=’9’) ret=ret10+(c-‘0’);
ret*=sgn;
return 1;
}
int main()
{
int n;
while(scanf(“%d”,&n) == 1){
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
init(n);
int u,v,w;
for(int i = 1;i < n;i++){
scan_d(u); scan_d(v);scan_d(w);
addedge(u,v,w);
addedge(v,u,w);
}
dfs(1,1);
int ans = node[1]->ms;
int Q;
char op[10];
scanf(“%d”,&Q);
while(Q–){
scanf(“%s”,op);
if(op[0] == ‘C’){
scan_d(u);
node[u]->access();
node[u]->splay();
if(node[u]->w0 == 0)node[u]->w0 = -INF;
else node[u]->w0 = 0;
node[u]->push_up();
ans = node[u]->ms;
}
else{
if(ans < 0)puts(“They have disappeared.”);
else printf(“%d\n”,ans);
}
}
}
return 0;
}

QTREE5

题意： 给定一棵n个结点的树，边权均为1。每个结点有黑白两色，初始时所有结点都是黑的。两种查询操作： 1.对一个结点执行反色操作（白变黑，黑变白） 2.查询距离某个特定结点i最远的白点的距离。 其中\(<=10^5\)，查询数目不超过\(10^5\). 比QTREE4简单，会QTREE4了这题简直很水。

/* ***
Author :kuangbin
Created Time :2014/8/28 20:57:35
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE5.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
//http://www.spoj.com/problems/QTREE5/
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
struct Node null;
struct Node{
Node \fa,*ch[2];
multisetst;
int dd,d0;
int w0;
int ls,rs;
inline void clear(){
fa = ch[0] = ch[1] = null;
st.clear();
st.insert(INF);
w0 = INF; dd = d0 = 0;
ls = rs = INF;
}
inline void push_up(){
if(this == null)return;
dd = d0 + ch[0]->dd + ch[1]->dd;
int m0 = min(w0,st.begin()), ml = min(m0,ch[0]->rs+d0), mr = min(m0,ch[1]->ls);
ls = min(ch[0]->ls,ch[0]->dd + d0 + mr);
rs = min(ch[1]->rs,ch[1]->dd + ml);
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay();
if(p->ch[1] != null){
p->st.insert(p->ch[1]->ls);
}
if(q != null){
p->st.erase(p->st.find(q->ls));
}
p->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
inline void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->st.clear();
null->ls = null->rs = INF;
null->w0 = INF;
null->dd = null->d0 = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->clear();
}
}
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
inline void addedge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
inline void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
node[v]->fa = node[u];
node[v]->d0 = 1;
dfs(v,u);
node[u]->st.insert(node[v]->ls);
}
node[u]->push_up();
}
int main()
{
int n;
while(scanf(“%d”,&n) == 1){
init(n);
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
int u,v;
for(int i = 1;i < n;i++){
scanf(“%d%d”,&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(1,1);
int Q;
scanf(“%d”,&Q);
int op;
while(Q–){
scanf(“%d%d”,&op,&v);
if(op == 0){
node[v]->access();
node[v]->splay();
if(node[v]->w0 == 0)node[v]->w0 = INF;
else node[v]->w0 = 0;
node[v]->push_up();
}
else {
node[v]->access();
node[v]->splay();
if(node[v]->rs < INF)printf(“%d\n”,node[v]->rs);
else printf(“-1\n”);
}
}
}
return 0;
}

QTREE6

题意： 给定一棵n个结点的树，每个结点有黑白两色，初始时所有结点都是黑的。你被要求支持： 1.对一个结点执行反色操作（白变黑，黑变白） 2.询问有多少个点与u相连。两个结点u,v相连当且仅当u,v路径上所有点的颜色相同。 其中\(n<=10^5\)，查询数目不超过\(10^5\). 维护和左右端点相连的点的个数ls,rs。 还有左右端点的颜色，自己的颜色，子树的两种颜色的总个数。 对于虚边维护两种颜色的总和就可以了。

/* ***
Author :kuangbin
Created Time :2014/8/28 21:44:01
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE6.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
//http://www.spoj.com/problems/QTREE6/
const int MAXN = 100010;
struct Node null;
struct Node{
Node \fa,*ch[2];
int co;//0 is black, 1 is white
int lco,rco;
int ls,rs;
int s[2];
int sum[2];//the sum of black and white
inline void clear(){
fa = ch[0] = ch[1] = null;
co = lco = rco = 0;
ls = rs = 1;
s[0] = s[1] = 0;
sum[0] = 1; sum[1] = 0;
}
inline void push_up(){
if(this == null)return;
if(ch[0] != null)lco = ch[0]->lco;
else lco = co;
if(ch[1] != null)rco = ch[1]->rco;
else rco = co;
sum[0] = ch[0]->sum[0] + ch[1]->sum[0] + (co == 0);
sum[1] = ch[0]->sum[1] + ch[1]->sum[1] + (co == 1);
int ml = 1 + s[co] + (co==ch[0]->rco?ch[0]->rs:0);
int mr = 1 + s[co] + (co==ch[1]->lco?ch[1]->ls:0);
ls = ch[0]->ls;
if(lco == co && ch[0]->sum[!co] == 0)ls += mr;
rs = ch[1]->rs;
if(rco == co && ch[1]->sum[!co] == 0)rs += ml;
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay();
if(p->ch[1] != null)
p->s[p->ch[1]->lco] += p->ch[1]->ls;
if(q != null)
p->s[q->lco] -= q->ls;
p->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->s[0] = null->s[1] = 0;
null->ls = null->rs = 0;
null->sum[0] = null->sum[1] = 0;
null->co = null->lco = null->rco = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->clear();
}
}
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
inline void addedge(int u,int v){
edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;
}
void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
node[v]->fa = node[u];
dfs(v,u);
node[u]->s[node[v]->lco] += node[v]->ls;
}
node[u]->push_up();
}
int main()
{
int n;
while(scanf(“%d”,&n) == 1){
init(n);
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
int u,v;
for(int i = 1;i < n;i++){
scanf(“%d%d”,&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(1,1);
int Q;
int op;
scanf(“%d”,&Q);
while(Q–){
scanf(“%d%d”,&op,&u);
if(op == 0){
node[u]->access();
node[u]->splay();
printf(“%d\n”,node[u]->rs);
}
else{
node[u]->access();
node[u]->splay();
node[u]->co ^= 1;
node[u]->push_up();
}
}
return 0;
}
return 0;
}

QTREE7

题意： 给定一棵n个结点的树，每个结点有黑白两色和权值。三种操作： 1.对一个结点执行反色操作（白变黑，黑变白） 2.询问与u相连的点中点权的最大值。两个结点u,v相连当且仅当u,v路径上所有点的颜色相同。 3.改变一个点的点权。 其中\(n<=10^5\)，查询数目不超过\(10^5\). 会了QTREE6，这题就简单了，增加set维护虚边。

/* ***
Author :kuangbin
Created Time :2014/8/29 9:09:44
File Name :E:\2014ACM\专题学习\数据结构\LCT\QTREE\SPOJQTREE7.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
//http://www.spoj.com/problems/QTREE7/
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
struct Node null;
struct Node{
Node \fa,*ch[2];
int co;
int lco,rco;
int ls,rs;
int w0;
multisetst[2];
int sum[2];
inline void clear(int _co = 0, int _w0 = 0){
fa = ch[0] = ch[1] = null;
co = lco = rco = _co;
w0 = _w0;
ls = rs = _w0;
st[0].clear(); st[1].clear();
st[0].insert(-INF); st[1].insert(-INF);
sum[0] = sum[1] = 0; sum[_co]++;
}
inline void push_up(){
if(this == null)return;
if(ch[0] != null)lco = ch[0]->lco;
else lco = co;
if(ch[1] != null)rco = ch[1]->rco;
else rco = co;
sum[0] = ch[0]->sum[0] + ch[1]->sum[0] + (co == 0);
sum[1] = ch[0]->sum[1] + ch[1]->sum[1] + (co == 1);
int ml = max(w0,max(st[co].rbegin(),co==ch[0]->rco?ch[0]->rs:-INF));
int mr = max(w0,max(st[co].rbegin(),co==ch[1]->lco?ch[1]->ls:-INF));
ls = ch[0]->ls;
if(lco == co && ch[0]->sum[!co] == 0)ls = max(ls,mr);
rs = ch[1]->rs;
if(rco == co && ch[1]->sum[!co] == 0)rs = max(rs,ml);
}
inline void setc(Node p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void rot(){
Node \f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node splay(){
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay();
if(p->ch[1] != null)
p->st[p->ch[1]->lco].insert(p->ch[1]->ls);
if(q != null)
p->st[q->lco].erase(p->st[q->lco].find(q->ls));
p->setc(q,1);
p->push_up();
}
return splay();
}
};
Node pool[MAXN],tail;
Node node[MAXN];
int color[MAXN],val[MAXN];
void init(int n){
tail = pool;
null = tail++;
null->fa = null->ch[0] = null->ch[1] = null;
null->st[0].clear(); null->st[1].clear();
null->ls = null->rs = -INF;
null->sum[0] = null->sum[1] = 0;
null->co = null->lco = null->rco = 0;
for(int i = 1;i <= n;i++){
node[i] = tail++;
node[i]->clear(color[i],val[i]);
}
}
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
inline void addedge(int u,int v){
edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;
}
void dfs(int u,int pre){
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == pre)continue;
node[v]->fa = node[u];
dfs(v,u);
node[u]->st[node[v]->lco].insert(node[v]->ls);
}
node[u]->push_up();
}
int main()
{
int n;
while(scanf(“%d”,&n) == 1){
for(int i = 1;i <= n;i++)head[i] = -1;
tot = 0;
int u,v;
for(int i = 1;i < n;i++){
scanf(“%d%d”,&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i = 1;i <= n;i++)scanf(“%d”,&color[i]);
for(int i = 1;i <= n;i++)scanf(“%d”,&val[i]);
init(n);
dfs(1,1);
int Q;
int w,op;
scanf(“%d”,&Q);
while(Q–){
scanf(“%d”,&op);
if(op == 0){
scanf(“%d”,&u);
node[u]->access(); node[u]->splay();
printf(“%d\n”,node[u]->rs);
}
else if(op == 1){
scanf(“%d”,&u);
node[u]->access(); node[u]->splay();
node[u]->co ^= 1;
node[u]->push_up();
}
else {
scanf(“%d%d”,&u,&w);
node[u]->access(); node[u]->splay();
node[u]->w0 = w;
node[u]->push_up();
}
}
}
return 0;
}

------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 363.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%