首页 > 代码库 > BZOJ1036;[ZJOI2008]树的统计

BZOJ1036;[ZJOI2008]树的统计

2024-11-10 23:56:39   204人阅读

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 17649  Solved: 7195
[Submit][Status][Discuss]

Description

　　一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

Input

　　输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有
一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作
的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output

　　对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16
 
 
　　没什么,一道水题,只是想用来练一练LCT....
#include<bits/stdc++.h>#define RG register#define il inline #define N 30010#define LL long longusing namespace std;struct ed{int nxt,to;}e[N*2];int head[N],tot;void add(int u,int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}void ADD(int u,int v){add(u,v),add(v,u);}int fa[N];void dfs(int u){for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=fa[u])fa[e[i].to]=u,dfs(e[i].to);}int Max[N],ch[N][2],st[N],n,v[N];bool rev[N];LL sum[N];int max(int x,int y){return x>y?x:y;}bool isroot(int x){return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}void down(int x){if(rev[x]){rev[x]^=1,rev[ch[x][1]]^=1,rev[ch[x][0]]^=1,swap(ch[x][1],ch[x][0]);}}void up(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x],Max[x]=max(max(Max[ch[x][1]],Max[ch[x][0]]),v[x]);}void Rotate(int x){  int y=fa[x],z=fa[y],l,r;  if(ch[y][0]==x)l=0;else l=1;r=l^1;  if(!isroot(y))ch[z][ch[z][1]==y]=x;  fa[x]=z,fa[y]=x;fa[ch[x][r]]=y;  ch[y][l]=ch[x][r],ch[x][r]=y;  up(y),up(x);}void Splay(int x){int y=x;  int top(0);st[++top]=x;  while(!isroot(y))st[++top]=fa[y],y=fa[y];  for(int i=top;i;i--)down(st[i]);  while(!isroot(x)){    y=fa[x];int z=fa[y];    if(!isroot(y)){      if(ch[z][0]==y^ch[y][0]==x)Rotate(x);      else Rotate(y);    }Rotate(x);  }up(x);}void access(int x){  int t=0;  while(x){    Splay(x);    ch[x][1]=t;    t=x;    up(x);    x=fa[x];  }}void rever(int x){  access(x);  Splay(x);  rev[x]^=1;}void querymax(int x,int y){  rever(x);  access(y);  Splay(y);  cout<<Max[y]<<"\n";}void querysum(int x,int y){  rever(x);  access(y);  Splay(y);  cout<<sum[y]<<"\n";}void change(int x,int kk){Splay(x),v[x]=kk,up(x);}int main(){  scanf("%d",&n);int u,V;memset(head,-1,sizeof(head));  for(int i=2;i<=n;++i)scanf("%d%d",&u,&V),ADD(u,V);Max[0]=-6666666;  for(int i=1;i<=n;++i)scanf("%d",&v[i]),sum[i]=Max[i]=v[i];;int Q;scanf("%d",&Q);  char s[6];dfs(1);  for(int i=1;i<=Q;++i){    scanf("%s",s);int x,y;scanf("%d%d",&x,&y);    if(s[0]==‘Q‘&&s[1]==‘M‘)querymax(x,y);    else if(s[0]==‘Q‘&&s[1]==‘S‘)querysum(x,y);    else change(x,y);  }return 0;}

　　

 

BZOJ1036;[ZJOI2008]树的统计


联系
我们