bzoj 5210(树链刨分下做个dp）

5210: 最大连通子块和

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 211 Solved: 65
[Submit][Status][Discuss]

Description

给出一棵n个点、以1为根的有根树，点有点权。要求支持如下两种操作：

M x y：将点x的点权改为y；

Q x：求以x为根的子树的最大连通子块和。

其中，一棵子树的最大连通子块和指的是：该子树所有子连通块的点权和中的最大值

（本题中子连通块包括空连通块，点权和为0）。

Input

第一行两个整数n、m，表示树的点数以及操作的数目。

第二行n个整数，第i个整数w_i表示第i个点的点权。

接下来的n-1行，每行两个整数x、y，表示x和y之间有一条边相连。

接下来的m行，每行输入一个操作，含义如题目所述。保证操作为M x y或Q x之一。

1≤n,m≤200000 ，任意时刻 |w_i|≤10^9 。

Output

对于每个Q操作输出一行一个整数，表示询问子树的最大连通子块和。

Sample Input

5 4
3 -2 0 3 -1
1 2
1 3
4 2
2 5
Q 1
M 4 1
Q 1
Q 2

Sample Output

4
3
1

我不知道什么动态dp，我只知道这是一个数据结构题。每次写个树链刨分都得弄半天orz。

大神题解：CQzhangyu

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define INF 0x3f3f3f3f
  5 #define LL long long
  6 #define pb push_back
  7 #define ls(i) (i<<1)
  8 #define rs(i) (i<<1|1)
  9 #define mp make_pair
 10 #define fi first
 11 #define se second
 12 using namespace std;
 13 const int N=2e5+10;
 14 int tsize[N];
 15 int son[N],down[N],top[N],dep[N],pos[N],pot[N],fat[N];
 16 int tot;
 17 int n,q;
 18 LL v[N],f[N],g[N],maxs[N];
 19 vector<int> e[N];
 20 struct heap
 21 {
 22     priority_queue<LL> ins,del;
 23     inline void push(LL x)
 24     {
 25         ins.push(x);
 26         return ;
 27     }
 28     inline void pop(LL x)
 29     {
 30         del.push(x);
 31         return ;
 32     }
 33     inline LL top()
 34     {
 35         while(!del.empty() && ins.top()==del.top())
 36             ins.pop(),del.pop();
 37         if(ins.empty()) return 0LL;
 38         return ins.top();
 39     }
 40     void pop()
 41     {
 42         top();
 43         del.push(ins.top());
 44         return ;
 45     }
 46 }lsq[N];
 47 void dfs1(int u,int d,int fa)
 48 {
 49 //    cout<<"begin:"<<u<<" "<<son[u]<<endl;
 50     dep[u]=d;
 51     tsize[u]=1;
 52     fat[u]=fa;
 53     int sz=e[u].size(),p;
 54     for(int i=0;i<sz;i++)
 55     {
 56         p=e[u][i];
 57 //        cout<<"branch:"<<u<<" "<<p<<" "<<fa<<endl;
 58         if(p!=fa)
 59         {
 60             dfs1(p,d+1,u);
 61             tsize[u]+=tsize[p];
 62             if(!son[u] || tsize[p]>tsize[son[u]])
 63                 son[u]=p;
 64         }
 65     }
 66 //    cout<<"endn:"<<u<<" "<<son[u]<<endl;
 67     return ;
 68 }
 69 void dfs2(int u,int tp)
 70 {
 71 //    cout<<u<<endl;
 72     top[u]=tp;
 73     pos[u]=++tot;
 74     pot[tot]=u;
 75     if(son[u]) dfs2(son[u],tp),down[u]=down[son[u]],maxs[u]=maxs[son[u]];
 76     else down[u]=u,maxs[u]=0;
 77     int sz=e[u].size();
 78     g[u]=v[u];
 79     for(int i=0;i<sz;i++)
 80     {
 81         int p=e[u][i];
 82         if(p!=fat[u] && p!=son[u])
 83         {
 84             dfs2(p,p);
 85             g[u]+=f[p];
 86             lsq[u].push(maxs[p]);
 87         }
 88     }
 89     f[u]=max(0LL,g[u]+f[son[u]]),maxs[u]=max(maxs[u],f[u]),maxs[u]=max(maxs[u],lsq[u].top());
 90     return ;
 91 }
 92 struct segt
 93 {
 94     int l,r;
 95     LL all,maxl,maxr,maxn;
 96     segt operator + (const segt &b)
 97     {
 98         segt p;
 99         p.maxl=max(maxl,all+b.maxl);
100         p.maxr=max(b.maxr,maxr+b.all);
101         p.all=all+b.all;
102         p.maxn=max(max(maxn,b.maxn),maxr+b.maxl);
103         p.l=l;
104         p.r=b.r;
105         return p;
106     }
107 }seg[N<<2];
108 void init(int i,int l,int r)
109 {
110     if(l==r)
111     {
112         int x=pot[l];
113         seg[i]=(segt){l,r,g[x],max(0LL,g[x]),max(0LL,g[x]),max(g[x],lsq[x].top())};
114         return ;
115     }
116     int mid=l+r>>1;
117     init(i<<1,l,mid);
118     init(i<<1|1,mid+1,r);
119     seg[i]=seg[i<<1]+seg[i<<1|1];
120     return ;
121 }
122 char s[10];
123 void refresh(int i,int pos)
124 {
125     if(seg[i].l==seg[i].r)
126     {
127         int x=pot[seg[i].l];
128         segt p=(segt){seg[i].l,seg[i].r,g[x],max(0LL,g[x]),max(0LL,g[x]),max(g[x],lsq[x].top())};
129         seg[i]=p;
130         return ;
131     }
132     int mid=seg[i].l+seg[i].r>>1;
133     if(mid>=pos) refresh(i<<1,pos);
134     else refresh(i<<1|1,pos);
135 
136     seg[i]=seg[i<<1]+seg[i<<1|1];
137     return ;
138 }
139 segt query(int i,int l,int r)
140 {
141     if(seg[i].l>=l && seg[i].r<=r)    return seg[i];
142     int mid=seg[i].l+seg[i].r>>1;
143     if(r<=mid)   return query(i<<1,l,r);
144     if(l>mid)    return query(i<<1|1,l,r);
145     return query(i<<1,l,r)+query(i<<1|1,l,r);
146 }
147 void update(int u,LL val)
148 {
149     segt t1,t2,t3;
150     bool flag=0;
151 //    cout<<u<<endl;
152     while(u)
153     {
154 //        cout<<u<<endl;
155         t3=query(1,pos[top[u]],pos[down[u]]);
156         if(flag)    lsq[u].pop(t1.maxn),lsq[u].push(t2.maxn);
157         t1=t3;
158         flag=1;
159         g[u]+=val,refresh(1,pos[u]);
160         t2=query(1,pos[top[u]],pos[down[u]]);
161         val=t2.maxl-f[top[u]],f[top[u]]=t2.maxl;
162         u=fat[top[u]];
163     }
164     return ;
165 }
166 int main()
167 {
168     tot=0;
169     scanf("%d%d",&n,&q);
170     for(int i=1;i<=n;i++)
171         scanf("%lld",v+i);
172     for(int i=2;i<=n;i++)
173     {
174         int u,v;
175         scanf("%d%d",&u,&v);
176         e[u].pb(v);
177         e[v].pb(u);
178     }
179     dfs1(1,1,0);
180     dfs2(1,1);
181     init(1,1,n);
182     for(int i=1;i<=q;i++)
183     {
184         scanf("%s",s);
185         if(s[0]=='M')
186         {
187             int u;
188             LL num;
189             scanf("%d%lld",&u,&num);
190             update(u,num-v[u]);
191             v[u]=num;
192         }
193         else
194         {
195             int u;
196             scanf("%d",&u);
197             printf("%lld
",query(1,pos[u],pos[down[u]]).maxn);
198         }
199     }
200     return 0;
201 }

View Code