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
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
3
1
我不知道什么动态dp，我只知道这是一个数据结构题。每次写个树链刨分都得弄半天orz。
大神题解：CQzhangyu
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=2e5+;
int tsize[N];
int son[N],down[N],top[N],dep[N],pos[N],pot[N],fat[N];
int tot;
int n,q;
LL v[N],f[N],g[N],maxs[N];
vector<int> e[N];
struct heap
{
priority_queue<LL> ins,del;
inline void push(LL x)
{
ins.push(x);
return ;
}
inline void pop(LL x)
{
del.push(x);
return ;
}
inline LL top()
{
while(!del.empty() && ins.top()==del.top())
ins.pop(),del.pop();
if(ins.empty()) return 0LL;
return ins.top();
}
void pop()
{
top();
del.push(ins.top());
return ;
}
}lsq[N];
void dfs1(int u,int d,int fa)
{
// cout<<"begin:"<<u<<" "<<son[u]<<endl;
dep[u]=d;
tsize[u]=;
fat[u]=fa;
int sz=e[u].size(),p;
for(int i=;i<sz;i++)
{
p=e[u][i];
// cout<<"branch:"<<u<<" "<<p<<" "<<fa<<endl;
if(p!=fa)
{
dfs1(p,d+,u);
tsize[u]+=tsize[p];
if(!son[u] || tsize[p]>tsize[son[u]])
son[u]=p;
}
}
// cout<<"endn:"<<u<<" "<<son[u]<<endl;
return ;
}
void dfs2(int u,int tp)
{
// cout<<u<<endl;
top[u]=tp;
pos[u]=++tot;
pot[tot]=u;
if(son[u]) dfs2(son[u],tp),down[u]=down[son[u]],maxs[u]=maxs[son[u]];
else down[u]=u,maxs[u]=;
int sz=e[u].size();
g[u]=v[u];
for(int i=;i<sz;i++)
{
int p=e[u][i];
if(p!=fat[u] && p!=son[u])
{
dfs2(p,p);
g[u]+=f[p];
lsq[u].push(maxs[p]);
}
}
f[u]=max(0LL,g[u]+f[son[u]]),maxs[u]=max(maxs[u],f[u]),maxs[u]=max(maxs[u],lsq[u].top());
return ;
}
struct segt
{
int l,r;
LL all,maxl,maxr,maxn;
segt operator + (const segt &b)
{
segt p;
p.maxl=max(maxl,all+b.maxl);
p.maxr=max(b.maxr,maxr+b.all);
p.all=all+b.all;
p.maxn=max(max(maxn,b.maxn),maxr+b.maxl);
p.l=l;
p.r=b.r;
return p;
}
}seg[N<<];
void init(int i,int l,int r)
{
if(l==r)
{
int x=pot[l];
seg[i]=(segt){l,r,g[x],max(0LL,g[x]),max(0LL,g[x]),max(g[x],lsq[x].top())};
return ;
}
int mid=l+r>>;
init(i<<,l,mid);
init(i<<|,mid+,r);
seg[i]=seg[i<<]+seg[i<<|];
return ;
}
char s[];
void refresh(int i,int pos)
{
if(seg[i].l==seg[i].r)
{
int x=pot[seg[i].l];
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())};
seg[i]=p;
return ;
}
int mid=seg[i].l+seg[i].r>>;
if(mid>=pos) refresh(i<<,pos);
else refresh(i<<|,pos); seg[i]=seg[i<<]+seg[i<<|];
return ;
}
segt query(int i,int l,int r)
{
if(seg[i].l>=l && seg[i].r<=r) return seg[i];
int mid=seg[i].l+seg[i].r>>;
if(r<=mid) return query(i<<,l,r);
if(l>mid) return query(i<<|,l,r);
return query(i<<,l,r)+query(i<<|,l,r);
}
void update(int u,LL val)
{
segt t1,t2,t3;
bool flag=;
// cout<<u<<endl;
while(u)
{
// cout<<u<<endl;
t3=query(,pos[top[u]],pos[down[u]]);
if(flag) lsq[u].pop(t1.maxn),lsq[u].push(t2.maxn);
t1=t3;
flag=;
g[u]+=val,refresh(,pos[u]);
t2=query(,pos[top[u]],pos[down[u]]);
val=t2.maxl-f[top[u]],f[top[u]]=t2.maxl;
u=fat[top[u]];
}
return ;
}
int main()
{
tot=;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
scanf("%lld",v+i);
for(int i=;i<=n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
e[v].pb(u);
}
dfs1(,,);
dfs2(,);
init(,,n);
for(int i=;i<=q;i++)
{
scanf("%s",s);
if(s[]=='M')
{
int u;
LL num;
scanf("%d%lld",&u,&num);
update(u,num-v[u]);
v[u]=num;
}
else
{
int u;
scanf("%d",&u);
printf("%lld\n",query(,pos[u],pos[down[u]]).maxn);
}
}
return ;
}