?

1036: [ZJOI2008]樹的統計Count

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?7980??Solved:?3266
[Submit][Status][Discuss]

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

HINT

第一次寫樹鏈剖分失敗了……一天沒搞出來，最后扒了個代碼。。不過真的跟自己寫的差不多，不想繼續找錯浪費時間，先保存下來好了……

?

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> using namespace std;const int MAXN = 30010; struct Edge {int to,next; }edge[MAXN*2]; int head[MAXN],tot; int top[MAXN]; //top[v] 表示v所在的重鏈的頂端節點 int fa[MAXN]; //父親節點 int deep[MAXN];//深度 int num[MAXN]; //num[v]表示以v為根的子樹的節點數 int p[MAXN]; //p[v]表示v在線段樹中的位置 int fp[MAXN];//和p數組相反 int son[MAXN];//重兒子 int pos; void init() {tot = 0;memset(head,-1,sizeof(head));pos = 0;memset(son,-1,sizeof(son)); } void addedge(int u,int v) {edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son {deep[u] = d;fa[u] = pre;num[u] = 1;for(int i = head[u];i != -1;i = edge[i].next){int v = edge[i].to;if(v != pre){dfs1(v,u,d+1);num[u] += num[v];if(son[u] == -1 || num[v] > num[son[u]])son[u] = v;}} } void getpos(int u,int sp) {top[u] = sp;p[u] = pos++;fp[p[u]] = u;if(son[u] == -1) return;getpos(son[u],sp);for(int i = head[u]; i != -1 ; i = edge[i].next){int v = edge[i].to;if(v != son[u] && v != fa[u]) getpos(v,v);} }struct Node {int l,r;int sum;int Max; }segTree[MAXN*3]; void push_up(int i) {segTree[i].sum = segTree[i<<1].sum + segTree[(i<<1)|1].sum;segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max); } int s[MAXN]; void build(int i,int l,int r) {segTree[i].l = l;segTree[i].r = r;if(l == r){segTree[i].sum = segTree[i].Max = s[fp[l]];return ;}int mid = (l + r)/2;build(i<<1,l,mid);build((i<<1)|1,mid+1,r);push_up(i); } void update(int i,int k,int val)//更新線段樹的第k個值為val {if(segTree[i].l == k && segTree[i].r == k){segTree[i].sum = segTree[i].Max = val;return;}int mid = (segTree[i].l + segTree[i].r)/2;if(k <= mid)update(i<<1,k,val);else update((i<<1)|1,k,val);push_up(i); } int queryMax(int i,int l,int r)//查詢線段樹[l,r]區間的最大值 {if(segTree[i].l == l && segTree[i].r == r){return segTree[i].Max;}int mid = (segTree[i].l + segTree[i].r)/2;if(r <= mid) return queryMax(i<<1,l,r);else if(l > mid)return queryMax((i<<1)|1,l,r);else return max(queryMax(i<<1,l,mid),queryMax((i<<1)|1,mid+1,r)); } int querySum(int i,int l,int r) //查詢線段樹[l,r]區間的和 {if(segTree[i].l == l && segTree[i].r == r)return segTree[i].sum;int mid = (segTree[i].l + segTree[i].r)/2;if(r <= mid)return querySum(i<<1,l,r);else if(l > mid)return querySum((i<<1)|1,l,r);else return querySum(i<<1,l,mid) + querySum((i<<1)|1,mid+1,r); } int findMax(int u,int v)//查詢u->v路徑上節點的最大權值 {int f1 = top[u] , f2 = top[v];int tmp = -1000000000;while(f1 != f2){if(deep[f1] < deep[f2]){swap(f1,f2);swap(u,v);}tmp = max(tmp,queryMax(1,p[f1],p[u]));u = fa[f1];f1 = top[u];}if(deep[u] > deep[v]) swap(u,v);return max(tmp,queryMax(1,p[u],p[v])); } int findSum(int u,int v) //查詢u->v路徑上節點的權值的和 {int f1 = top[u], f2 = top[v];int tmp = 0;while(f1 != f2){if(deep[f1] < deep[f2]){swap(f1,f2);swap(u,v);}tmp += querySum(1,p[f1],p[u]);u = fa[f1];f1 = top[u];}if(deep[u] > deep[v]) swap(u,v);return tmp + querySum(1,p[u],p[v]); } int main() {int n;int q;char op[20];int u,v;scanf("%d",&n);init();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",&s[i]);dfs1(1,0,0);getpos(1,1);build(1,0,pos-1);scanf("%d",&q);while(q--){scanf("%s%d%d",op,&u,&v);if(op[0] == 'C') update(1,p[u],v); else if(strcmp(op,"QMAX") == 0)printf("%d\n",findMax(u,v));else printf("%d\n",findSum(u,v));}return 0; }

以上為滿分代碼

?

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; char c[10]; int t,n,z,m,a,b,u,v,q,f1,f2,cost[30010],w[30010],tree[30010],tree0[30010],fw[30010],top[30010],size[30010],son[30010],head[30010],next[60010],list[60010],fa[30010],dep[30010]; void insert(int x,int y) {next[++m]=head[x];head[x]=m;list[m]=y; } void dfs(int v) {size[v]=1; for (int i=head[v];i;i=next[i])if (list[i]!=fa[v]) {fa[list[i]]=v;dep[list[i]]=dep[v]+1;dfs(list[i]);if (size[list[i]]>size[son[v]]) son[v]=list[i];size[v]+=size[list[i]];} } void build_tree(int v,int tp) {w[v]=++z;fw[w[v]]=v;top[v]=tp;if (son[v]!=0) build_tree(son[v],tp);for (int i=head[v];i;i=next[i])if (list[i]!=son[v]&&list[i]!=fa[v])build_tree(list[i],list[i]); } void build(int root,int l,int r) {if (l==r){tree[root]=tree0[root]=cost[fw[root]];return;}int mid=(l+r)/2;build(root*2,1,mid);build(root*2+1,mid+1,r);tree[root]=max(tree[root*2],tree[root*2+1]);tree0[root]=tree0[root*2]+tree0[root*2+1]; } void updata(int root,int l,int r,int pos,int x) {if (pos>r||pos<l) return;int mid=(l+r)/2;if (l==r) {tree[root]=x;tree0[root]=x;return;}updata(root*2,l,mid,pos,x);updata(root*2+1,mid+1,r,pos,x);tree[root]=max(tree[root*2],tree[root*2+1]);tree0[root]=tree0[root*2]+tree0[root*2+1]; } int maxi(int root,int l,int r,int ll,int rr) {if (l==ll&&r==rr) return tree[root];int mid=(l+r)/2;if (rr<=mid) return maxi(root*2,l,mid,ll,rr);else if (ll>mid) return maxi(root*2+1,mid+1,r,ll,rr);else return max(maxi(root*2,l,mid,ll,mid),maxi(root*2+1,mid+1,r,mid+1,rr)); } int find(int va,int vb) {int f1=top[va],f2=top[vb],tmp=-1000000;while (f1!=f2){if (dep[f1]<dep[f2]) {swap(va,vb);swap(f1,f2);}tmp=max(tmp,maxi(1,1,z,w[f1],w[va]));va=fa[f1]; f1=top[va];}if (dep[va]>dep[vb]) swap(va,vb);return max(tmp,maxi(1,1,z,w[va],w[vb])); } int sumi(int root,int l,int r,int ll,int rr) {if (l==ll&&r==rr) return tree0[root];int mid=(l+r)/2;if (rr<=mid) return sumi(root*2,l,mid,ll,rr);else if (ll>mid) return sumi(root*2+1,mid+1,r,ll,rr);else return sumi(root*2,l,mid,ll,mid)+sumi(root*2+1,mid+1,r,mid+1,rr); } int calc(int va,int vb) {int f1=top[va],f2=top[vb],tmp=0;while (f1!=f2){if (dep[f1]<dep[f2]){swap(va,vb);swap(f1,f2);}tmp+=sumi(1,1,z,w[f1],w[va]);va=fa[f1]; f1=top[va];}if (dep[va]>dep[vb]) swap(va,vb);return tmp+sumi(1,1,z,w[va],w[vb]); } int main() {freopen("count.in","r",stdin);//freopen("count.out","w",stdout);scanf("%d",&n);for (int i=1;i<n;i++){scanf("%d%d",&u,&v);insert(u,v);insert(v,u);}for (int i=1;i<=n;i++) scanf("%d",&cost[i]);dfs(1);build_tree(1,1);build(1,1,z);for (int i=1;i<=n;i++) updata(1,1,z,w[i],cost[i]);scanf("%d",&q);for (int i=1;i<=q;i++){scanf("%s",c);scanf("%d%d",&u,&v);if (c[0]=='C') updata(1,1,z,w[u],v);if (c[1]=='M') printf("%d\n",find(u,v));if (c[1]=='S') printf("%d\n",calc(u,v));}return 0; }

我的殘廢代碼。

轉載于:https://www.cnblogs.com/ws-fqk/p/4641410.html

總結

以上是生活随笔為你收集整理的[ZJOI2008][BZOJ1036] 树的统计count的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。