BZOJ 1036: [ZJOI2008]树的统计Count 树链剖分
1036: 树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 6769 Solved: 2772
Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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
代码我抄HZWER的，正在学习
//qscqesze#include <cstdio>#include <cmath>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <set>#include <vector>#include <sstream>#include <queue>#include <typeinfo>#include <fstream>#include <map>#include <stack>typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200001#define mod 10007#define eps 1e-9int Num;char CH;//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;/*inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH+48); puts("");}*/inline ll read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH+48); puts("");}//**************************************************************************************#define N 1000000#define M 1000000int n,q,cnt,sz;int fa,v,deep,size,head;int pos,belong;bool vis;struct data{ int to,next;}e;struct seg{ int l,r,mx,sum;}t;void insert(int u,int v){ e[++cnt].to=v;e.next=head;head=cnt; e[++cnt].to=u;e.next=head;head=cnt;}void ini(){ scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); insert(x,y); } for(int i=1;i<=n;i++) scanf("%d",&v);}void dfs1(int x){ size=1; vis=1; for(int i=1;i<=14;i++) { if(deep<(1<<i)) break; fa=fa]; } for(int i=head;i;i=e.next) { if(vis.to]) continue; deep.to]=deep+1; fa.to]=x; dfs1(e.to); size+=size.to]; }}//第一遍dfs求出树每个结点的深度deep，其为根的子树大小size//以及祖先的信息fa表示x往上距离为2^i的祖先void dfs2(int x,int chain){ int k=0; sz++; pos=sz; belong=chain; for(int i=head;i;i=e.next) if(deep.to]>deep&&size.to]>size) k=e.to; if(k==0) return; dfs2(k,chain); for(int i=head;i;i=e.next) if(deep.to]>deep&&k!=e.to) dfs2(e.to,e.to);}int lca(int x,int y){ if(deep<deep) swap(x,y); int t=deep-deep; for(int i=0;i<=14;i++) if(t&(1<<i)) x=fa; for(int i=14;i>=0;i--) { if(fa!=fa) { x=fa; y=fa; } } if(x==y) return x; else return fa;}void build(int k,int l,int r){ t.l=l,t.r=r; if(l==r) return ; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);}void change(int k,int x,int y){ int l=t.l,r=t.r,mid=(l+r)>>1; if(l==r) { t.sum=t.mx=y; return; } if(x<=mid) change(k<<1,x,y); else change(k<<1|1,x,y); t.sum=t.sum+t.sum; t.mx=max(t.mx,t.mx);}int querysum(int k,int x,int y){ int l=t.l,r=t.r,mid=(l+r)>>1; if(l==x&&y==r) return t.sum; if(y<=mid)return querysum(k<<1,x,y); else if(x>mid)return querysum(k<<1|1,x,y); else return querysum(k<<1,x,mid)+querysum(k<<1|1,mid+1,y);}int querymx(int k,int x,int y){ int l=t.l,r=t.r,mid=(l+r)>>1; if(l==x&&y==r)return t.mx; if(y<=mid)return querymx(k<<1,x,y); else if(x>mid)return querymx(k<<1|1,x,y); else return max(querymx(k<<1,x,mid),querymx(k<<1|1,mid+1,y));}int solvesum(int x,int f){ int sum=0; while(belong!=belong) { sum+=querysum(1,pos],pos); x=fa]; } sum+=querysum(1,pos,pos); return sum;}int solvemx(int x,int f){ int mx=-inf; while(belong!=belong) { mx=max(mx,querymx(1,pos],pos)); x=fa]; } mx=max(mx,querymx(1,pos,pos)); return mx;}void solve(){ build(1,1,n); for(int i=1;i<=n;i++) change(1,pos,v); scanf("%d",&q); char ch; for(int i=1;i<=q;i++) { int x,y; scanf("%s%d%d",ch,&x,&y); if(ch=='C') { v=y; change(1,pos,y); } else { int t=lca(x,y); if(ch=='M') printf("%d\n",max(solvemx(x,t),solvemx(y,t))); else printf("%d\n",solvesum(x,t)+solvesum(y,t)-v); } }}int main(){ ini(); dfs1(1); dfs2(1,1); solve();}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3111018
页:
[1]