bzoj 1036: [ZJOI2008]树的统计Count

树剖板子

然而不停WA....

注意：

1.分清pos[a],arr[a];曾经116行pos[a]写成a，WA

2.134行曾经复制的时候没改，成了qmax(..)

3.126,137行这里没有a!=b或其他的判断语句，直接查询

4.133行不是dep[a]<dep[b]，这里是比较链顶点的深度，相当于比较两个点向上跳一次之后的深度，而不是自身的深度

5.46行不要写成maxn[l]，a[num],a[l],...注意线段树上点的下标是num，原数据一定要按a[arr[l]]取

6.各个取最大值的函数初始值要为-inf，而各个取和的函数初始值要为0

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 typedef long long LL;
  5 struct E
  6 {
  7     LL to,nxt;
  8 }e[60100];
  9 LL f1[30100],ne;
 10 LL hson[30100],f[30100],sz[30100],arr[30100],pos[30100],top[30100],dep[30100];
 11 LL aa[30100];
 12 void dfs1(LL u,LL fa)
 13 {
 14     sz[u]=1;
 15     for(LL k=f1[u];k;k=e[k].nxt)
 16         if(e[k].to!=fa)
 17         {
 18             dep[e[k].to]=dep[u]+1;
 19             dfs1(e[k].to,u);
 20             sz[u]+=sz[e[k].to];
 21             if(sz[hson[u]]<sz[e[k].to])    hson[u]=e[k].to;
 22         }
 23 }
 24 void dfs2(LL u,LL fa)
 25 {
 26     arr[++arr[0]]=u;pos[u]=arr[0];
 27     f[u]=fa;
 28     if(u==hson[fa])    top[u]=top[fa];
 29     else    top[u]=u;
 30     if(hson[u])    dfs2(hson[u],u);
 31     for(LL k=f1[u];k;k=e[k].nxt)
 32         if(e[k].to!=fa&&e[k].to!=hson[u])
 33         {
 34             dfs2(e[k].to,u);
 35         }
 36 }
 37 LL n,q;
 38 namespace SegT
 39 {
 40 #define mid (l+((r-l)>>1))
 41 #define lc (num<<1)
 42 #define rc (num<<1|1)
 43     LL maxn[120100],sum[120100];
 44     void build(LL l,LL r,LL num)
 45     {
 46         if(l==r)    {maxn[num]=sum[num]=aa[arr[l]];return;}
 47         build(l,mid,lc);build(mid+1,r,rc);
 48         maxn[num]=max(maxn[lc],maxn[rc]);
 49         sum[num]=sum[lc]+sum[rc];
 50     }
 51     LL L,R,x;
 52     void _update(LL l,LL r,LL num)
 53     {
 54         if(l==r)    {maxn[num]=sum[num]=x;return;}
 55         if(L<=mid)    _update(l,mid,lc);
 56         else    _update(mid+1,r,rc);
 57         maxn[num]=max(maxn[lc],maxn[rc]);
 58         sum[num]=sum[lc]+sum[rc];
 59     }
 60     LL _qmax(LL l,LL r,LL num)
 61     {
 62         if(L<=l&&r<=R)    return maxn[num];
 63         LL ans=-0x3f3f3f3f;
 64         if(L<=mid)    ans=max(ans,_qmax(l,mid,lc));
 65         if(mid<R)    ans=max(ans,_qmax(mid+1,r,rc));
 66         return ans;
 67     }
 68     LL _qsum(LL l,LL r,LL num)
 69     {
 70         if(L<=l&&r<=R)    return sum[num];
 71         LL ans=0;
 72         if(L<=mid)    ans+=_qsum(l,mid,lc);
 73         if(mid<R)    ans+=_qsum(mid+1,r,rc);
 74         return ans;
 75     }
 76     void update(LL a,LL b)
 77     {
 78         L=a;x=b;_update(1,n,1);
 79     }
 80     LL qmax(LL l,LL r)
 81     {
 82         L=l;R=r;if(L>R)    swap(L,R);
 83         return _qmax(1,n,1);
 84     }
 85     LL qsum(LL l,LL r)
 86     {
 87         L=l;R=r;if(L>R)    swap(L,R);
 88         return _qsum(1,n,1);
 89     }
 90 #undef mid
 91 #undef lc
 92 #undef rc
 93 }
 94 using SegT::qmax;
 95 using SegT::qsum;
 96 int main()
 97 {
 98     LL i,a,b,ans;char tmp[10];
 99     scanf("%lld",&n);
100     for(i=1;i<n;i++)
101     {
102         scanf("%lld%lld",&a,&b);
103         e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
104         e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
105     }
106     for(i=1;i<=n;i++)    scanf("%lld",&aa[i]);
107     dfs1(1,0);dfs2(1,0);
108     SegT::build(1,n,1);
109     scanf("%lld",&q);
110     while(q--)
111     {
112         scanf("%s%lld%lld",tmp,&a,&b);
113         switch(tmp[1])
114         {
115         case 'H':
116             SegT::update(pos[a],b);
117             break;
118         case 'M':
119             ans=-0x3f3f3f3f;
120             while(top[a]!=top[b])
121             {
122                 if(dep[top[a]]<dep[top[b]])    swap(a,b);
123                 ans=max(ans,qmax(pos[a],pos[top[a]]));
124                 a=f[top[a]];
125             }
126             ans=max(ans,qmax(pos[a],pos[b]));
127             printf("%lld
",ans);
128             break;
129         case 'S':
130             ans=0;
131             while(top[a]!=top[b])
132             {
133                 if(dep[top[a]]<dep[top[b]])    swap(a,b);//不是dep[a]<dep[b]
134                 ans+=qsum(pos[a],pos[top[a]]);//曾经不小心复制错，成了qmax(...)
135                 a=f[top[a]];
136             }
137             ans+=qsum(pos[a],pos[b]);//没有if(a!=b)
138             printf("%lld
",ans);
139             break;
140         }
141     }
142     return 0;
143 }