Bzoj 1036: [ZJOI2008]树的统计Count

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 17222 Solved: 7033
[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

这是立志换码风（多打几个回车）后的第一个题

写完之后拼命地wa，自己瞎改了两下，随手删了几个小地方，就A了

我也不知道为什么

  1 /*
  2     qsum和qmax两个函数中的if(x!=y)要去掉
  3     主函数中的特判if(x==y)printf("%d
",value[x]);和if(x==y)printf("%d
",value[x]);要去掉
  4 */
  5 #include<iostream>
  6 #include<cstdio>
  7 using namespace std;
  8 
  9 #define maxn 300100
 10 #define inf 0x7fffffff
 11 int m,n,head[maxn],num,dep[maxn],son[maxn],sz[maxn],pos[maxn],top[maxn],idx,father[maxn],value[maxn];
 12 
 13 struct edge{
 14     int to,pre;
 15 }e[maxn*3];
 16 
 17 void addedge(int from,int to){
 18     e[++num].to=to;
 19     e[num].pre=head[from];
 20     head[from]=num;
 21     
 22     e[++num].to=from;
 23     e[num].pre=head[to];
 24     head[to]=num;
 25 }
 26 
 27 void dfs_find(int fa,int u){
 28     dep[u]=dep[fa]+1;
 29     sz[u]=1;
 30     son[u]=0;
 31     father[u]=fa;
 32     for(int i=head[u];i;i=e[i].pre){
 33         int v=e[i].to;
 34         if(v==fa)continue;
 35         dfs_find(u,v);
 36         sz[u]+=sz[v];
 37         if(sz[v]>sz[son[u]]||son[u]==0)son[u]=v;
 38     }
 39 }
 40 
 41 void dfs_time(int fa,int u){
 42     pos[u]=++idx;top[u]=fa;
 43     if(son[u]!=0)dfs_time(top[u],son[u]);
 44     for(int i=head[u];i;i=e[i].pre){
 45         int v=e[i].to;
 46         if(v==father[u]||v==son[u])continue;
 47         dfs_time(v,v);
 48     }
 49 }
 50 
 51 struct tree{
 52     int l,r,mx,sum;
 53 }tr[maxn<<2];
 54 void build(int l,int r,int k){
 55     tr[k].l=l;tr[k].r=r;tr[k].mx=-inf;tr[k].sum=0;
 56     if(l==r)return;
 57     int mid=(l+r)>>1;
 58     build(l,mid,k<<1);
 59     build(mid+1,r,k<<1|1);
 60 }
 61 void update(int p,int v,int k){
 62     if(tr[k].l==tr[k].r){tr[k].mx=tr[k].sum=v;return;}
 63     int mid=(tr[k].l+tr[k].r)>>1;
 64     if(p<=mid)update(p,v,k<<1);
 65     else if(p>mid)update(p,v,k<<1|1);
 66     tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
 67     tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
 68 }
 69 int findsum(int l,int r,int k){
 70     if(tr[k].l==l&&tr[k].r==r)return tr[k].sum;
 71     int mid=(tr[k].l+tr[k].r)>>1;
 72     if(r<=mid)return findsum(l,r,k<<1);
 73     else if(l>mid)return findsum(l,r,k<<1|1);
 74     else return findsum(l,mid,k<<1)+findsum(mid+1,r,k<<1|1);
 75 }
 76 int qsum(int x,int y){
 77     int ans=0;
 78     while(top[x]!=top[y]){
 79         if(dep[top[x]]<dep[top[y]])swap(x,y);
 80         ans+=findsum(pos[top[x]],pos[x],1);
 81         x=father[top[x]];
 82     }
 83     if(dep[x]>dep[y])swap(x,y);
 84     if(x!=y)ans+=findsum(pos[x],pos[y],1);
 85     return ans;
 86 }
 87 int findmax(int l,int r,int k){
 88     if(tr[k].l==l&&tr[k].r==r)return tr[k].mx;
 89     int mid=(tr[k].l+tr[k].r)>>1;
 90     if(r<=mid)return findmax(l,r,k<<1);
 91     else if(l>mid)return findmax(l,r,k<<1|1);
 92     else return max(findmax(l,mid,k<<1),findmax(mid+1,r,k<<1|1));
 93 }
 94 int qmax(int x,int y){
 95     int ans=-inf;
 96     while(top[x]!=top[y]){
 97         if(dep[top[x]]<dep[top[y]])swap(x,y);
 98         ans=max(ans,findmax(pos[top[x]],pos[x],1));
 99         x=father[top[x]];
100     }
101     if(dep[x]>dep[y])swap(x,y);
102     if(x!=y)ans=max(ans,findmax(pos[x],pos[y],1));
103     return ans;
104 }
105 char c[10];
106 int main(){
107     scanf("%d",&n);
108     int x,y;
109     for(int i=1;i<n;i++){
110         scanf("%d%d",&x,&y);
111         addedge(x,y);
112     }
113     idx=0;
114     dfs_find(1,1);
115     dfs_time(1,1);
116     build(1,n,1);
117     for(int i=1;i<=n;i++){
118         scanf("%d",&value[i]);
119         update(pos[i],value[i],1);
120     }
121     
122     scanf("%d",&m);
123     for(int i=1;i<=m;i++){
124         scanf("%s",c);scanf("%d%d",&x,&y);
125         if(c[1]=='S'){
126             if(x==y)printf("%d
",value[x]);
127             else printf("%d
",qsum(x,y));
128         }
129         if(c[1]=='M'){
130             if(x==y)printf("%d
",value[x]);
131             else printf("%d
",qmax(x,y));
132         }
133         
134         if(c[1]=='H')update(pos[x],y,1);
135     }
136 }

10分两处小八哥

  1 #include<iostream>
  2 #include<cstdio>
  3 using namespace std;
  4 
  5 #define maxn 300100
  6 #define inf 0x7fffffff
  7 int m,n,head[maxn],num,dep[maxn],son[maxn],sz[maxn],pos[maxn],top[maxn],idx,father[maxn],value[maxn];
  8 
  9 struct edge{
 10     int to,pre;
 11 }e[maxn*3];
 12 
 13 void addedge(int from,int to){
 14     e[++num].to=to;
 15     e[num].pre=head[from];
 16     head[from]=num;
 17     
 18     e[++num].to=from;
 19     e[num].pre=head[to];
 20     head[to]=num;
 21 }
 22 
 23 void dfs_find(int fa,int u){
 24     dep[u]=dep[fa]+1;
 25     sz[u]=1;
 26     son[u]=0;
 27     father[u]=fa;
 28     for(int i=head[u];i;i=e[i].pre){
 29         int v=e[i].to;
 30         if(v==fa)continue;
 31         dfs_find(u,v);
 32         sz[u]+=sz[v];
 33         if(sz[v]>sz[son[u]]||son[u]==0)son[u]=v;
 34     }
 35 }
 36 
 37 void dfs_time(int fa,int u){
 38     pos[u]=++idx;top[u]=fa;
 39     if(son[u]!=0)dfs_time(top[u],son[u]);
 40     for(int i=head[u];i;i=e[i].pre){
 41         int v=e[i].to;
 42         if(v==father[u]||v==son[u])continue;
 43         dfs_time(v,v);
 44     }
 45 }
 46 
 47 struct tree{
 48     int l,r,mx,sum;
 49 }tr[maxn<<2];
 50 void build(int l,int r,int k){
 51     tr[k].l=l;tr[k].r=r;tr[k].mx=-inf;tr[k].sum=0;
 52     if(l==r)return;
 53     int mid=(l+r)>>1;
 54     build(l,mid,k<<1);
 55     build(mid+1,r,k<<1|1);
 56 }
 57 void update(int p,int v,int k){
 58     if(tr[k].l==tr[k].r){tr[k].mx=tr[k].sum=v;return;}
 59     int mid=(tr[k].l+tr[k].r)>>1;
 60     if(p<=mid)update(p,v,k<<1);
 61     else if(p>mid)update(p,v,k<<1|1);
 62     tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
 63     tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
 64 }
 65 int findsum(int l,int r,int k){
 66     if(tr[k].l==l&&tr[k].r==r)return tr[k].sum;
 67     int mid=(tr[k].l+tr[k].r)>>1;
 68     if(r<=mid)return findsum(l,r,k<<1);
 69     else if(l>mid)return findsum(l,r,k<<1|1);
 70     else return findsum(l,mid,k<<1)+findsum(mid+1,r,k<<1|1);
 71 }
 72 int qsum(int x,int y){
 73     int ans=0;
 74     while(top[x]!=top[y]){
 75         if(dep[top[x]]<dep[top[y]])swap(x,y);
 76         ans+=findsum(pos[top[x]],pos[x],1);
 77         x=father[top[x]];
 78     }
 79     if(dep[x]>dep[y])swap(x,y);
 80     /*if(x!=y)*/ans+=findsum(pos[x],pos[y],1);
 81     return ans;
 82 }
 83 int findmax(int l,int r,int k){
 84     if(tr[k].l==l&&tr[k].r==r)return tr[k].mx;
 85     int mid=(tr[k].l+tr[k].r)>>1;
 86     if(r<=mid)return findmax(l,r,k<<1);
 87     else if(l>mid)return findmax(l,r,k<<1|1);
 88     else return max(findmax(l,mid,k<<1),findmax(mid+1,r,k<<1|1));
 89 }
 90 int qmax(int x,int y){
 91     int ans=-inf;
 92     while(top[x]!=top[y]){
 93         if(dep[top[x]]<dep[top[y]])swap(x,y);
 94         ans=max(ans,findmax(pos[top[x]],pos[x],1));
 95         x=father[top[x]];
 96     }
 97     if(dep[x]>dep[y])swap(x,y);
 98     /*if(x!=y)*/ans=max(ans,findmax(pos[x],pos[y],1));
 99     return ans;
100 }
101 char c[10];
102 int main(){
103     scanf("%d",&n);
104     int x,y;
105     for(int i=1;i<n;i++){
106         scanf("%d%d",&x,&y);
107         addedge(x,y);
108     }
109     idx=0;
110     dfs_find(1,1);
111     dfs_time(1,1);
112     build(1,n,1);
113     for(int i=1;i<=n;i++){
114         scanf("%d",&value[i]);
115         update(pos[i],value[i],1);
116     }
117     
118     scanf("%d",&m);
119     for(int i=1;i<=m;i++){
120         scanf("%s",c);scanf("%d%d",&x,&y);
121         if(c[1]=='S') printf("%d
",qsum(x,y));
122         if(c[1]=='M') printf("%d
",qmax(x,y));
123         
124         if(c[1]=='H')update(pos[x],y,1);
125     }
126 }

100 分