【学习】树链剖分
联赛不会树链剖分就GG了。。所以要加把劲补一补辣
也就是几道题。。。背板要紧是么。。
然而还是没有背熟QAQ
这里还是个坑
通常用来维护的数据结构是线段树，所以感觉学了这个顺便弄好了线段树
第一遍dfs
求出树每个结点的深度deep[x]，其为根的子树大小sz[x]
以及祖先的信息fa[x][i]表示x往上距离为$2^i$的祖先(lca)
第二遍dfs
根节点为起点，向下拓展构建重链,选择最大的一个子树的根继承当前重链
其余节点都以该节点为起点向下重新拉一条重链
给每个结点分配一个位置编号，每条重链就相当于一段区间维护。
把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可
修改&查询操作
1、单独修改一个点的权值
根据其编号直接在数据结构中修改就行了。
2、修改点u和点v的路径上的权值
（1）若u和v在同一条重链上,直接用数据结构修改pos[u]至pos[v]间的值。
（2）若u和v不在同一条重链上,一边进行修改，一边将u和v往同一条重链上靠，然后就变成了情况（1）
可以去膜lbn187的 用树链剖分解决LCA问题
以及这个讲得比较清楚的blog
BZOJ-2243
第一次做树链剖分呢
直接树链剖分+线段树（感觉窝要通过树链剖分学习线段树了怎么办QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cmath>
#define NN 100010
using namespace std;
int n,m,tot=0,size,head[NN],fa[NN][20],deep[NN],sz[NN],b[NN],pl[NN],c[NN],x,y,z;
bool vis[NN];
char ch[10];
struct REC
{
int ne,v;
}e[NN<<1];
struct Tree
{
int lc,rc,l,r,tag,s;
}tree[NN<<2];
void Build(int xx,int yy)
{
e[++tot].ne=head[xx]; head[xx]=tot; e[tot].v=yy;
e[++tot].ne=head[yy]; head[yy]=tot; e[tot].v=xx;
}
void DFS1(int xx)
{
vis[xx]=sz[xx]=1;
for (int i=1;i<=17;++i)
{
if (deep[xx]<(1<<i)) break;
fa[xx][i]=fa[fa[xx][i-1]][i-1];
}
for (int i=head[xx];i;i=e[i].ne)
if (!vis[e[i].v])
{
fa[e[i].v][0]=xx;
deep[e[i].v]=deep[xx]+1;
DFS1(e[i].v);
sz[xx]+=sz[e[i].v];
}
}
void DFS2(int xx,int yy)
{
pl[xx]=++size; b[xx]=yy;
int tmp=0;
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && sz[e[i].v]>sz[tmp]) tmp=e[i].v;
if (!tmp) return;
DFS2(tmp,yy);
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && e[i].v!=tmp) DFS2(e[i].v,e[i].v);
}
void Build_Tree(int p,int ll,int rr)
{
tree[p].l=ll,tree[p].r=rr,tree[p].s=1,tree[p].tag=-1;
if (ll==rr) return;
int mid=(ll+rr)>>1;
Build_Tree(p<<1,ll,mid); Build_Tree(p<<1|1,mid+1,rr);
}
void push_up(int p)
{
tree[p].lc=tree[p<<1].lc,tree[p].rc=tree[p<<1|1].rc;
if (tree[p<<1].rc^tree[p<<1|1].lc) tree[p].s=tree[p<<1].s+tree[p<<1|1].s;
else tree[p].s=tree[p<<1].s+tree[p<<1|1].s-1;
}
void push_down(int p)
{
int tmp=tree[p].tag; tree[p].tag=-1;
if (tmp==-1||tree[p].l==tree[p].r) return;
tree[p<<1].s=tree[p<<1|1].s=1;
tree[p<<1].tag=tree[p<<1|1].tag=tmp;
tree[p<<1].lc=tree[p<<1].rc=tree[p<<1|1].lc=tree[p<<1|1].rc=tmp;
}
void Change(int p,int xx,int yy,int cc)
{
push_down(p);
int l=tree[p].l,r=tree[p].r;
if (l==xx&&r==yy)
{
tree[p].lc=tree[p].rc=cc,tree[p].s=1,tree[p].tag=cc; return;
}
int mid=(l+r)>>1;
if (mid>=yy) Change(p<<1,xx,yy,cc);
else if (mid<xx) Change(p<<1|1,xx,yy,cc);
else Change(p<<1,xx,mid,cc),Change(p<<1|1,mid+1,yy,cc);
push_up(p);
}
int ask(int p,int xx,int yy)
{
push_down(p);
int l=tree[p].l,r=tree[p].r;
if (l==xx&&r==yy) return tree[p].s;
int mid=(l+r)>>1;
if (mid>=yy) return ask(p<<1,xx,yy);
else if (mid<xx) return ask(p<<1|1,xx,yy);
else
{
int tmp=1;
if (tree[p<<1].rc^tree[p<<1|1].lc) tmp=0;
return ask(p<<1,xx,mid)+ask(p<<1|1,mid+1,yy)-tmp;
}
}
int get_c(int p,int xx)
{
push_down(p);
int l=tree[p].l,r=tree[p].r;
if (l==r) return tree[p].lc;
int mid=(l+r)>>1;
if (xx<=mid) return get_c(p<<1,xx);
else return get_c(p<<1|1,xx);
}
int sum(int xx,int tt)
{
int summ=0;
while (b[xx]!=b[tt])
{
summ+=ask(1,pl[b[xx]],pl[xx]);
if (get_c(1,pl[b[xx]])==get_c(1,pl[fa[b[xx]][0]])) summ--;
xx=fa[b[xx]][0];
}
summ+=ask(1,pl[tt],pl[xx]);
return summ;
}
void c_color(int xx,int tt,int cc)
{
while (b[xx]!=b[tt])
Change(1,pl[b[xx]],pl[xx],cc),xx=fa[b[xx]][0];
Change(1,pl[tt],pl[xx],cc);
}
int LCA(int xx,int yy)
{
if (deep[xx]<deep[yy]) swap(xx,yy);
int tmp=deep[xx]-deep[yy];
for (int i=0;i<=17;++i)
if (tmp&(1<<i)) xx=fa[xx][i];
for (int i=17;i>=0;--i)
if (fa[xx][i]!=fa[yy][i])
xx=fa[xx][i],yy=fa[yy][i];
if (xx==yy) return xx;
else return fa[xx][0];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%d",&c[i]);
for (int i=1;i<n;++i) scanf("%d%d",&x,&y),Build(x,y);
DFS1(1);
DFS2(1,1);
Build_Tree(1,1,n);
for (int i=1;i<=n;++i) Change(1,pl[i],pl[i],c[i]);
for (int i=1;i<=m;++i)
{
scanf("%s",ch);
if (ch[0]=='Q')
{
scanf("%d%d",&x,&y);
int tmp=LCA(x,y);
printf("%d\n",sum(x,tmp)+sum(y,tmp)-1);
}
else
{
scanf("%d%d%d",&x,&y,&z);
int tmp=LCA(x,y);
c_color(x,tmp,z),c_color(y,tmp,z);
}
}
return 0;
}
感觉果真写了树链剖分，线段树都开始6起来惹。。。才不会说【Training Contest】2016.03.08里面的线段树就是在做完这道题后写的QAQ
BZOJ-4196
某NOI题。。。当时好像是我第一次听说树链剖分这种东西QAQ（蒟蒻真渣
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define NN 800100
using namespace std;
int n,m,x,y,now,tot=0,size=0,sz[NN],head[NN],father[NN],pos[NN],belong[NN],deep[NN];
char ch[50];
bool vis[NN];
struct REC
{
int ne,v;
}e[NN];
struct T
{
int l,r,key,tag,sum;
}tree[NN];
void Build(int xx,int yy)
{
e[++tot].v=yy,e[tot].ne=head[xx],head[xx]=tot;
}
void DFS1(int xx)
{
vis[xx]=1,sz[xx]=1;
for (int i=head[xx];i;i=e[i].ne)
if (!vis[e[i].v])
{
deep[e[i].v]=deep[xx]+1,father[e[i].v]=xx;
DFS1(e[i].v); sz[xx]+=sz[e[i].v];
}
}
void DFS2(int xx,int yy)
{
int now=0;
pos[xx]=++size; belong[xx]=yy;
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && sz[e[i].v]>sz[now]) now=e[i].v;
if (!now) return;
DFS2(now,yy);
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && e[i].v!=now)
DFS2(e[i].v,e[i].v);
}
void push_up(int p)
{
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
void push_down(int p)
{
if (tree[p].tag)
{
tree[p<<1].sum=(tree[p<<1].r-tree[p<<1].l+1)*tree[p].key;
tree[p<<1|1].sum=(tree[p<<1|1].r-tree[p<<1|1].l+1)*tree[p].key;
tree[p<<1].tag=tree[p<<1|1].tag=1;
tree[p<<1].key=tree[p<<1|1].key=tree[p].key;
tree[p].tag=tree[p].key=0;
}
}
void Build_tree(int p,int l,int r)
{
tree[p].l=l,tree[p].r=r;
int mid=(l+r)>>1;
if (l==r) { tree[p].sum=1; return;}
Build_tree(p<<1,l,mid); Build_tree(p<<1|1,mid+1,r);
push_up(p);
}
int query(int p,int x,int y) //才不会说把x打成了s调试了一个多小时
{
push_down(p);
if (x<=tree[p].l && tree[p].r<=y) return tree[p].sum;
int l=tree[p].l,r=tree[p].r,mid=(l+r)>>1;
if (x>mid) return query(p<<1|1,x,y);
else if (y<=mid) return query(p<<1,x,y);
else return query(p<<1,x,mid)+query(p<<1|1,mid+1,y);
}
void Insert(int k,int x,int y,int key){
push_down(k);
if(x<=tree[k].l&&tree[k].r<=y){
tree[k].sum=(tree[k].r-tree[k].l+1)*key;
tree[k].tag=1;
tree[k].key=key;
return;
}
int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1;
if(x>mid)Insert(k<<1|1,x,y,key);
else if(y<=mid)Insert(k<<1,x,y,key);
else Insert(k<<1,x,mid,key),Insert(k<<1|1,mid+1,y,key);
push_up(k);
}
int main()
{
scanf("%d",&n);
for (int i=2;i<=n;++i)
{
int x;
scanf("%d",&x); Build(x+1,i);
}
DFS1(1);
DFS2(1,1);
Build_tree(1,1,n);
scanf("%d",&m);
while (m--)
{
scanf("%s",ch); scanf("%d",&x); ++x;
if (ch[0]=='i')
{
now=0;
for (;belong[x]!=belong[1];x=father[belong[x]])
{
now+=query(1,pos[belong[x]],pos[x]);
Insert(1,pos[belong[x]],pos[x],0);
}
now+=query(1,pos[belong[x]],pos[x]);
Insert(1,pos[belong[x]],pos[x],0);
printf("%d\n",now);
}
else
{
int l=pos[x],r=pos[x]+sz[x]-1;
now=sz[x]-query(1,l,r);
Insert(1,l,r,1);
printf("%d\n",now);
}
}
return 0;
}
BZOJ-3631
松鼠的新家是一棵树。我们要求出每一个房间被访问的次数，也就是我们要在每一次从一个房间出发到达另一个房间的过程中对于路径上的节点权值进行+1操作,用线段树+lazy标记维护点权。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#define NN 300100
using namespace std;
int n,tot=0,a[NN],head[NN],deep[NN],sz[NN],son[NN],top[NN],w[NN],num=0,fa[NN];
struct TREE
{
int l,r,mid,s,lazy;
}tree[NN<<2];
struct REC
{
int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
e[++tot].ne=head[xx], e[tot].v=yy, head[xx]=tot;
e[++tot].ne=head[yy], e[tot].v=xx, head[yy]=tot;
}
void DFS1(int xx)
{
sz[xx]=1;
for (int i=head[xx];i;i=e[i].ne)
{
if (e[i].v!=fa[xx])
{
deep[e[i].v]=deep[xx]+1, fa[e[i].v]=xx;
DFS1(e[i].v);
sz[xx]+=sz[e[i].v];
if (sz[son[xx]]<sz[e[i].v]) son[xx]=e[i].v;
}
}
}
void DFS2(int xx,int st)
{
w[xx]=++num, top[xx]=st;
if (!son[xx]) return;
DFS2(son[xx],st);
for (int i=head[xx];i;i=e[i].ne)
if (e[i].v!=fa[xx] && e[i].v!=son[xx]) DFS2(e[i].v,e[i].v);
}
void push_up(int p) {tree[p].s=tree[p<<1].s+tree[p<<1|1].s;}
void push_down(int p,int len)
{
tree[p<<1].s+=(len-(len>>1))*tree[p].lazy;
tree[p<<1|1].s+=(len>>1)*tree[p].lazy;
tree[p<<1].lazy+=tree[p].lazy;
tree[p<<1|1].lazy+=tree[p].lazy;
tree[p].lazy=0;
}
void Build_tree(int p,int l,int r)
{
tree[p].l=l, tree[p].r=r, tree[p].mid=(l+r)>>1;
if (l==r) { tree[p].s=0; return;}
Build_tree(p<<1,l,tree[p].mid), Build_tree(p<<1|1,tree[p].mid+1,r);
}
void Change(int p,int ll,int rr,int k)
{
if (ll<=tree[p].l && tree[p].r<=rr)
{
tree[p].s+=(tree[p].r-tree[p].l+1)*k; tree[p].lazy+=k; return;
}
if (tree[p].lazy!=0) push_down(p,tree[p].r-tree[p].l+1);
if (ll<=tree[p].mid) Change(p<<1,ll,rr,k);
if (rr>tree[p].mid) Change(p<<1|1,ll,rr,k);
push_up(p);
}
int Query(int p,int xx)
{
if (tree[p].l==tree[p].r) return tree[p].s;
if (tree[p].lazy!=0) push_down(p,tree[p].r-tree[p].l+1);
if (xx<=tree[p].mid) return Query(p<<1,xx);
return Query(p<<1|1,xx);
}
void Work(int xx,int yy)
{
int y=yy;
if (deep[top[xx]]<deep[top[yy]]) swap(xx,yy);
while (top[xx]!=top[yy])
{
if (deep[top[xx]]<deep[top[yy]]) swap(xx,yy);
Change(1,w[top[xx]],w[xx],1);
xx=fa[top[xx]];
}
if (deep[xx]<deep[yy]) swap(xx,yy);
Change(1,w[yy],w[xx],1);
Change(1,w[y],w[y],-1);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y), Build(x,y);
}
DFS1(1), DFS2(1,1);
Build_tree(1,1,num);
for (int i=1;i<n;++i) Work(a[i],a[i+1]);
for (int i=1;i<=n;++i)
printf("%d\n",Query(1,w[i]));
return 0;
}
BZOJ-1036
感觉应该是很典型的树链剖分吧。。然而蒟蒻调试了好久
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define NN 30010
#define INF 0x3f3f3f3f
using namespace std;
char ch[10];
int a[NN],deep[NN],fa[NN][20],head[NN],pos[NN],belong[NN],tot=0,sz[NN],num=0,n,m;
bool vis[NN];
struct REC
{
int ne,v;
}e[NN<<1];
struct TREE
{
int l,r,mid,sum,mx;
}tree[NN<<2];
inline void Build(int xx,int yy)
{
e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy;
e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx;
}
inline void DFS1(int xx)
{
sz[xx]=1; vis[xx]=1;
for (int i=1;i<=14;++i)
if (deep[xx]<(1<<i)) break;
else fa[xx][i]=fa[fa[xx][i-1]][i-1];
for (int i=head[xx];i;i=e[i].ne)
if (!vis[e[i].v])
{
fa[e[i].v][0]=xx; deep[e[i].v]=deep[xx]+1;
DFS1(e[i].v);
sz[xx]+=sz[e[i].v];
}
}
inline void DFS2(int xx,int chain)
{
pos[xx]=++num; belong[xx]=chain;
int tmp=0;
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && sz[e[i].v]>sz[tmp]) tmp=e[i].v;
if (!tmp) return;
DFS2(tmp,chain);
for (int i=head[xx];i;i=e[i].ne)
if (deep[e[i].v]>deep[xx] && e[i].v!=tmp) DFS2(e[i].v,e[i].v);
}
inline void push_up(int p)
{
tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
inline void Build_tree(int p,int l,int r)
{
tree[p].l=l, tree[p].r=r; tree[p].mid=(l+r)>>1;
if (l==r) return;
int mid=tree[p].mid;
Build_tree(p<<1,l,mid), Build_tree(p<<1|1,mid+1,r);
}
inline void Change(int p,int x,int y)
{
if (tree[p].l==tree[p].r) { tree[p].mx=tree[p].sum=y; return;}
int mid=tree[p].mid;
if (x<=mid) Change(p<<1,x,y);
else Change(p<<1|1,x,y);
push_up(p);
}
inline int Getsum(int p,int l,int r)
{
if (tree[p].l==l && tree[p].r==r) return tree[p].sum;
int mid=tree[p].mid;
if (r<=mid) return Getsum(p<<1,l,r);
else if (l>mid) return Getsum(p<<1|1,l,r);
else return Getsum(p<<1,l,mid)+Getsum(p<<1|1,mid+1,r);
}
inline int Getmx(int p,int l,int r)
{
if (tree[p].l==l && r==tree[p].r) return tree[p].mx;
int mid=tree[p].mid;
if (r<=mid) return Getmx(p<<1,l,r);
else if (l>mid) return Getmx(p<<1|1,l,r);
else return max(Getmx(p<<1,l,mid),Getmx(p<<1|1,mid+1,r));
}
inline int Ssum(int x,int f)
{
int sum=0;
while (belong[x]!=belong[f])
{
sum+=Getsum(1,pos[belong[x]],pos[x]);
x=fa[belong[x]][0];
}
sum+=Getsum(1,pos[f],pos[x]);
return sum;
}
inline int Smax(int x,int f)
{
int mx=-INF;
while (belong[x]!=belong[f])
{
mx=max(mx,Getmx(1,pos[belong[x]],pos[x]));
x=fa[belong[x]][0];
}
mx=max(mx,Getmx(1,pos[f],pos[x]));
return mx;
}
inline int lca(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
int t=int(log2(deep[x]-deep[y]));
for (int i=t;i>=0;--i)if (deep[x]-(1<<i)>=deep[y]) x=fa[x][i];
if (x==y) return x;
t=int(log2(deep[x]));
for (int i=t;i>=0;--i) if (fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y); Build(x,y);
}
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
memset(vis,0,sizeof(vis));
DFS1(1), DFS2(1,1);
Build_tree(1,1,n);
for (int i=1;i<=n;++i) Change(1,pos[i],a[i]);
scanf("%d",&m);
while (m--)
{
int x,y;
scanf("%s",ch); scanf("%d%d",&x,&y);
if (ch[1]=='H') a[x]=y, Change(1,pos[x],y);
else
{
int tmp=lca(x,y);
if (ch[1]=='M') printf("%d\n",max(Smax(x,tmp),Smax(y,tmp)));
else printf("%d\n",Ssum(x,tmp)+Ssum(y,tmp)-a[tmp]);
}
}
return 0;
}
--- update 20160712 ---
黈力上课讲树剖
于是就又来打补丁辣
BZOJ-3531
对于每种宗教都建立一棵线段树，即可维护辣
然而这样内存会爆 (╯‵□′)╯︵┻━┻
所以我们要用动态开节点的线段树QAQ
对于每个节点，我们额外维护它左右节点的下标，这样我们可以一边操作一边添加节点
其他的好像和平常的树剖并没有什么大的差别QAQ
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define NN 100010
int n,Q,sz = 0,idd= 0,tot= 0,x,y;
char ch[20];
int rt[NN],c[NN],w[NN],belong[NN],fa[NN],size[NN]={0},deep[NN],id[NN],head[NN];
struct Tree
{
int l,r,maxx,sum;
}tr[4000010];
struct E
{
int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
}
void DFS1(int xx)
{
size[xx] = 1;
for (int i=head[xx];i;i=e[i].ne)
if (e[i].v != fa[xx])
{
fa[e[i].v] = xx;
deep[e[i].v] = deep[xx] + 1;
DFS1(e[i].v);
size[xx] += size[e[i].v];
}
}
void DFS2(int xx,int chain)
{
belong[xx] = chain, id[xx] = ++sz;
int now = 0;
for (int i=head[xx];i;i=e[i].ne) if (deep[xx] < deep[e[i].v] && size[now] < size[e[i].v]) now = e[i].v;
if (!now) return;
DFS2(now,chain);
for (int i=head[xx];i;i=e[i].ne) if (e[i].v != fa[xx] && now != e[i].v) DFS2(e[i].v,e[i].v);
}
void push_up(int p)
{
tr[p].maxx = max(tr[tr[p].l].maxx, tr[tr[p].r].maxx);
tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum;
}
void update(int &now,int l,int r,int pos,int ww)
{
if (!now) now = ++idd;
if (l == r)
{
tr[now].maxx = tr[now].sum = ww;
return;
}
int mid = (l+r) >> 1 ;
if (pos <= mid) update(tr[now].l,l,mid,pos,ww);
else update(tr[now].r,mid+1,r,pos,ww);
push_up(now);
}
int Get_sum(int p,int L,int R,int l,int r)
{
if (L >= l && R <= r) return tr[p].sum;
int mid = (L+R) >> 1, ans = 0;
if (mid >= l) ans += Get_sum(tr[p].l,L,mid,l,r);
if (mid < r) ans += Get_sum(tr[p].r,mid+1,R,l,r);
return ans;
}
int Get_max(int p,int L,int R,int l,int r)
{
if (L >= l && R <= r) return tr[p].maxx;
int mid = (L+R) >> 1, ans = 0;
if (mid >= l) ans = max(ans,Get_max(tr[p].l,L,mid,l,r));
if (mid < r) ans = max(ans,Get_max(tr[p].r,mid+1,R,l,r));
return ans;
}
void Solve_sum(int cc,int l,int r)
{
int ans = 0;
for (;belong[l] != belong[r];l = fa[belong[l]])
{
if (deep[belong[l]] < deep[belong[r]]) swap(l,r);
ans += Get_sum(rt[cc],1,sz,id[belong[l]],id[l]);
}
if (deep[l] > deep[r]) swap(l,r);
ans += Get_sum(rt[cc],1,sz,id[l],id[r]);
printf("%d\n",ans);
}
void Solve_max(int cc,int l,int r)
{
int ans = 0;
for (;belong[l] != belong[r];l = fa[belong[l]])
{
if (deep[belong[l]] < deep[belong[r]]) swap(l,r);
ans = max(ans,Get_max(rt[cc],1,sz,id[belong[l]],id[l]));
}
if (deep[l] > deep[r]) swap(l,r);
ans = max(ans,Get_max(rt[cc],1,sz,id[l],id[r]));
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&Q);
for (int i=1;i<=n;++i) scanf("%d%d",&w[i],&c[i]);
for (int i=1;i<n;++i) scanf("%d%d",&x,&y), Build(x,y);
DFS1(1); DFS2(1,1);
for (int i=1;i<=n;++i) update(rt[c[i]],1,sz,id[i],w[i]);
while (Q--)
{
scanf("%s",ch);
scanf("%d%d",&x,&y);
if (ch[0] == 'C')
{
if (ch[1] == 'C')
update(rt[c[x]],1,n,id[x],0), c[x] = y, update(rt[c[x]],1,n,id[x],w[x]);
else
update(rt[c[x]],1,n,id[x],y), w[x] = y;
}
else
{
if (ch[1] == 'S') Solve_sum(c[x],x,y);
else Solve_max(c[x],x,y);
}
}
return 0;
}
//调试的时候被自己手敲样例弄死
lujiaxin
搜索
乱七八糟的分类
友链墙
计数君
42994
标签君
100题
200题
2016
2017
404题
AC自动机
CDQ分治
Contest
DP
Heap
KMP
Learning
Lerning
Manacher
NOIP
Person Of Interest
SPFA
Splay
ZHOJ
ZJOI
a+b
bzoj
hash
vijos
wc
主席树
单纯形法
可并堆
后缀自动机
启发式合并
回文自动机
图论
字符串
学习
平衡树
数学
数论
树
树分治
树链剖分
游记
生活
留念
算法
线段树
网络流
美剧
莫队算法
计算几何
费用流
辩论
高斯消元
2023年7月07日 00:15
Initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country Our team comprises of professional writers journal with diverse range of interest in Journalism samplepaper.in who are passionate about publishing the Education Updates with transparency in general public interest.