正文
Cogs 1583. [POJ3237]树的维护 LCT,树链剖分
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目：http://cojs.tk/cogs/problem/problem.php?pid=1583
1583. [POJ3237]树的维护
★★★☆ 输入文件：
maintaintree.in
输出文件：
maintaintree.out
简单对比
时间限制：5 s 内存限制：128 MB
【题目描述】
给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：
CHANGE i v：将第i条边的权值改成v。
NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。
QUERY a b：找出点a到点b路径上各边的最大权值。
【输入格式】
输入文件的第一行有一个整数N（N<=10000）。
接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。
接下来是若干条指令（不超过10^5条），都按照上面所说的格式。
输入文件的最后一行是"DONE".
【输出格式】
对每个“QUERY”指令，输出一行，即路径上各边的最大权值。
【样例输入】
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【样例输出】
1
3
【提示】
这里的输入输出格式和POJ上原题略有不同。
【来源】
POJ 3237 Tree
题解：
LCT维护一下最大值和最小值，当要变为相反数时，把 最大值变为原来的最小值的相反数，最小值变为原来最大值的相反数 即可。。。
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAXN 10010
struct node
{
int left,right,mx,mn,val;
}tree[*MAXN];
int rev[*MAXN],tag[*MAXN],father[*MAXN],Stack[*MAXN],n;
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
int isroot(int x)
{
return tree[father[x]].left!=x&&tree[father[x]].right!=x;
}
void pushdown(int x)
{
int l=tree[x].left,r=tree[x].right;
if(rev[x]!=)
{
rev[x]^=;rev[l]^=;rev[r]^=;
swap(tree[x].left,tree[x].right);
}
if(tag[x]!=)
{
tag[x]^=;tag[l]^=;tag[r]^=;
tree[l].val=-tree[l].val;
tree[r].val=-tree[r].val;
swap(tree[l].mx,tree[l].mn);
tree[l].mx=-tree[l].mx;tree[l].mn=-tree[l].mn;
swap(tree[r].mx,tree[r].mn);
tree[r].mx=-tree[r].mx;tree[r].mn=-tree[r].mn;
}
}
void pushup(int x)
{
int l=tree[x].left,r=tree[x].right;
tree[x].mx=max(tree[l].mx,tree[r].mx);
if(x>n)tree[x].mx=max(tree[x].mx,tree[x].val);
tree[x].mn=min(tree[l].mn,tree[r].mn);
if(x>n)tree[x].mn=min(tree[x].mn,tree[x].val);
}
void rotate(int x)
{
int y=father[x],z=father[y];
if(!isroot(y))
{
if(tree[z].left==y)tree[z].left=x;
else tree[z].right=x;
}
if(tree[y].left==x)
{
father[x]=z;father[y]=x;tree[y].left=tree[x].right;tree[x].right=y;father[tree[y].left]=y;
}
else
{
father[x]=z;father[y]=x;tree[y].right=tree[x].left;tree[x].left=y;father[tree[y].right]=y;
}
pushup(y);pushup(x);
}
void splay(int x)
{
int top=,i,y,z;Stack[++top]=x;
for(i=x;!isroot(i);i=father[i])Stack[++top]=father[i];
for(i=top;i>=;i--)pushdown(Stack[i]);
while(!isroot(x))
{
y=father[x],z=father[y];
if(!isroot(y))
{
if((tree[y].left==x)^(tree[z].left==y))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
int last=;
while(x!=)
{
splay(x);
tree[x].right=last;pushup(x);
last=x;x=father[x];
}
}
void makeroot(int x)
{
access(x);splay(x);rev[x]^=;
}
void link(int u,int v)
{
makeroot(u);father[u]=v;splay(u);
}
void cut(int u,int v)
{
makeroot(u);access(v);splay(v);father[u]=tree[v].left=;
}
int findroot(int x)
{
access(x);splay(x);
while(tree[x].left!=)x=tree[x].left;
return x;
}
int main()
{
freopen("maintaintree.in","r",stdin);
freopen("maintaintree.out","w",stdout);
int i,a,b,c;
char fh[];
n=read();
for(i=;i<=*n;i++)tree[i].mx=-INF,tree[i].mn=INF;
for(i=;i<n;i++)
{
a=read();b=read();c=read();
tree[n+i].mx=tree[n+i].mn=tree[n+i].val=c;
link(a,n+i);link(n+i,b);
}
while()
{
scanf("\n%s",fh);
if(fh[]=='D')break;
if(fh[]=='Q')
{
a=read();b=read();
makeroot(a);access(b);splay(b);
printf("%d\n",tree[b].mx);
}
else if(fh[]=='C')
{
a=read();b=read();
makeroot(n+a);tree[n+a].mn=tree[n+a].mx=tree[n+a].val=b;
}
else
{
a=read();b=read();
makeroot(a);access(b);splay(b);
tag[b]^=;
swap(tree[b].mx,tree[b].mn);
tree[b].val=-tree[b].val;
tree[b].mx=-tree[b].mx;
tree[b].mn=-tree[b].mn;
}
}
fclose(stdin);
fclose(stdout);
return ;
}
2016.3.24
补一发树链剖分:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define INF 1e9
struct node
{
int begin,end,value,next;
}edge[*MAXN];
struct NODE
{
int left,right,mx,mn,tag;
}tree[*MAXN];
int cnt,Head[MAXN],n,size[MAXN],deep[MAXN],P[MAXN][],pos[MAXN],belong[MAXN],id[MAXN],vv[MAXN],U[MAXN],V[MAXN],VAL[MAXN],SIZE;
bool vis[MAXN];
void addedge(int bb,int ee,int vv)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee,int vv)
{
addedge(bb,ee,vv);addedge(ee,bb,vv);
}
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void dfs1(int u)
{
int i,v;
size[u]=;vis[u]=true;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(vis[v]==false)
{
deep[v]=deep[u]+;
P[v][]=u;
dfs1(v);
size[u]+=size[v];
}
}
}
void Ycl()
{
int i,j;
for(j=;(<<j)<=n;j++)
{
for(i=;i<=n;i++)
{
if(P[i][j-]!=-)P[i][j]=P[P[i][j-]][j-];
}
}
}
void dfs2(int u,int chain)
{
int k=,i,v;
pos[u]=++SIZE;belong[u]=chain;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&size[v]>size[k])k=v;
}
if(k==)return;
dfs2(k,chain);
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&v!=k)dfs2(v,v);
}
}
int LCA(int x,int y)
{
int i,j;
if(deep[x]<deep[y])swap(x,y);
for(i=;(<<i)<=deep[x];i++);i--;
for(j=i;j>=;j--)if(deep[x]-(<<j)>=deep[y])x=P[x][j];
if(x==y)return x;
for(j=i;j>=;j--)
{
if(P[x][j]!=-&&P[x][j]!=P[y][j])
{
x=P[x][j];
y=P[y][j];
}
}
return P[x][];
}
void Pushup(int k)
{
tree[k].mx=max(tree[k*].mx,tree[k*+].mx);
tree[k].mn=min(tree[k*].mn,tree[k*+].mn);
}
void Pushdown(int k)
{
int l=k*,r=k*+;
if(tree[k].tag!=)
{
tree[k].tag^=;tree[l].tag^=;tree[r].tag^=;
swap(tree[l].mn,tree[l].mx);
tree[l].mn=-tree[l].mn;tree[l].mx=-tree[l].mx;
swap(tree[r].mn,tree[r].mx);
tree[r].mn=-tree[r].mn;tree[r].mx=-tree[r].mx;
}
}
void Build(int k,int l,int r)
{
tree[k].left=l;tree[k].right=r;tree[k].mx=-INF;tree[k].mn=INF;tree[k].tag=;
if(l==r)
{
tree[k].mx=tree[k].mn=vv[l];
return;
}
int mid=(l+r)/;
Build(k*,l,mid);Build(k*+,mid+,r);
Pushup(k);
}
void Change(int k,int lr,int C)
{
if(tree[k].left==tree[k].right){tree[k].mx=tree[k].mn=C;return;}
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(lr<=mid)Change(k*,lr,C);
else Change(k*+,lr,C);
Pushup(k);
}
int Query_max(int k,int l,int r)
{
if(l<=tree[k].left&&tree[k].right<=r)return tree[k].mx;
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)return Query_max(k*,l,r);
else if(l>mid)return Query_max(k*+,l,r);
else return max(Query_max(k*,l,mid),Query_max(k*+,mid+,r));
}
int Solve_max(int x,int f)
{
int MAX=-INF;
while(belong[x]!=belong[f])
{
MAX=max(MAX,Query_max(,pos[belong[x]],pos[x]));
x=P[belong[x]][];
}
if(x!=f)MAX=max(MAX,Query_max(,pos[f]+,pos[x]));
return MAX;
}
void Negate(int k,int l,int r)
{
if(l<=tree[k].left&&tree[k].right<=r/*tree[k].left==tree[k].right*/)
{
swap(tree[k].mn,tree[k].mx);
tree[k].mn=-tree[k].mn;tree[k].mx=-tree[k].mx;
tree[k].tag^=;
return;
}
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)Negate(k*,l,r);
else if(l>mid)Negate(k*+,l,r);
else {Negate(k*,l,mid);Negate(k*+,mid+,r);}
Pushup(k);
}
void Solve_negate(int x,int f)
{
while(belong[x]!=belong[f])
{
Negate(,pos[belong[x]],pos[x]);
x=P[belong[x]][];
}
if(x!=f)Negate(,pos[f]+,pos[x]);
}
int main()
{
freopen("maintaintree.in","r",stdin);
freopen("maintaintree.out","w",stdout);
int i,I,W,bb,ee,lca;
char fh[];
n=read();
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<n;i++)
{
U[i]=read();V[i]=read();VAL[i]=read();
addedge1(U[i],V[i],VAL[i]);
}
memset(P,-,sizeof(P));SIZE=;
dfs1();Ycl();
dfs2(,);
for(i=;i<n;i++)
{
if(deep[U[i]]>deep[V[i]])id[i]=U[i];
else id[i]=V[i];
}
for(i=;i<n;i++)vv[pos[id[i]]]=VAL[i];
Build(,,n);
while()
{
scanf("\n%s",fh);
if(fh[]=='D')break;
if(fh[]=='C')
{
I=read();W=read();
Change(,pos[id[I]],W);
}
else if(fh[]=='Q')
{
bb=read();ee=read();
lca=LCA(bb,ee);
printf("%d\n",max(Solve_max(bb,lca),Solve_max(ee,lca)));
}
else
{
bb=read();ee=read();
lca=LCA(bb,ee);
Solve_negate(bb,lca);
Solve_negate(ee,lca);
}
}
fclose(stdin);
fclose(stdout);
return ;
}
