1.【bzoj4034】[HAOI2015]T2
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000000
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,cnt;
int last[];
int id,pos[],mx[],v[];
int bl[],size[],fa[];
ll tag[],sum[];
struct edge{
int to,next;
}e[];
void insert(int u,int v)
{
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs(int x)
{
size[x]=;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x])
{
fa[e[i].to]=x;
dfs(e[i].to);
size[x]+=size[e[i].to];
mx[x]=max(mx[x],mx[e[i].to]);
}
}
void dfs2(int x,int cha)
{
bl[x]=cha;pos[x]=mx[x]=++id;
int k=;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x]&&size[e[i].to]>size[k])
k=e[i].to;
if(k)
{
dfs2(k,cha);mx[x]=max(mx[x],mx[k]);
}
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x]&&e[i].to!=k)
{
dfs2(e[i].to,e[i].to);
mx[x]=max(mx[x],mx[e[i].to]);
}
}
void pushdown(int l,int r,int k)
{
if(l==r)return;
int mid=(l+r)>>;ll t=tag[k];tag[k]=;
tag[k<<]+=t;tag[k<<|]+=t;
sum[k<<]+=t*(mid-l+);
sum[k<<|]+=t*(r-mid);
}
void add(int k,int l,int r,int x,int y,ll val)
{
if(tag[k])pushdown(l,r,k);
if(l==x&&y==r){tag[k]+=val;sum[k]+=(r-l+)*val;return;}
int mid=(l+r)>>;
if(x<=mid)add(k<<,l,mid,x,min(mid,y),val);
if(y>=mid+)add(k<<|,mid+,r,max(mid+,x),y,val);
sum[k]=sum[k<<]+sum[k<<|];
}
ll query(int k,int l,int r,int x,int y)
{
if(tag[k])pushdown(l,r,k);
if(l==x&&y==r)return sum[k];
int mid=(l+r)>>;
ll ans=;
if(x<=mid)
ans+=query(k<<,l,mid,x,min(mid,y));
if(y>=mid+)
ans+=query(k<<|,mid+,r,max(mid+,x),y);
return ans;
}
ll query(int x)
{
ll ans=;
while(bl[x]!=)
{
ans+=query(,,n,pos[bl[x]],pos[x]);
x=fa[bl[x]];
}
ans+=query(,,n,,pos[x]);
return ans;
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)v[i]=read();
for(int i=;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
dfs();
dfs2(,);
for(int i=;i<=n;i++)
add(,,n,pos[i],pos[i],v[i]);
int opt,x,a;
while(m--)
{
opt=read();x=read();
if(opt==)
{
a=read();add(,,n,pos[x],pos[x],a);
}
if(opt==)
{
a=read();add(,,n,pos[x],mx[x],a);
}
if(opt==)printf("%lld\n",query(x));
}
return ;
}
2.【bzoj2243】[SDOI2011]染色
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define N 100001
using namespace std;
int n,m,cnt,sz,head[N],deep[N],son[N],belong[N],pl[N],v[N],ft[N][];
bool vis[N];
struct seg{int l,r,lc,rc,s,tag;}t[*N];
struct edge{int to,next;}e[*N];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void dfs1(int x)
{
vis[x]=son[x]=;
for(int i=;i<=;i++)
{
if(deep[x]<(<<i))break;
ft[x][i]=ft[ft[x][i-]][i-];
}
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
deep[e[i].to]=deep[x]+;
ft[e[i].to][]=x;
dfs1(e[i].to);
son[x]+=son[e[i].to];
}
}
void dfs2(int x,int chain)
{
pl[x]=++sz;belong[x]=chain;
int k=;
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&son[k]<son[e[i].to])
k=e[i].to;
if(!k)return;
dfs2(k,chain);
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&k!=e[i].to)
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if(t&(<<i))x=ft[x][i];
for(int i=;i>=;i--)
if(ft[x][i]!=ft[y][i])
{x=ft[x][i];y=ft[y][i];}
if(x==y)return x;
return ft[x][];
}
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].s=;t[k].tag=-;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void pushup(int k)
{
t[k].lc=t[k<<].lc;t[k].rc=t[k<<|].rc;
if(t[k<<].rc^t[k<<|].lc)t[k].s=t[k<<].s+t[k<<|].s;
else t[k].s=t[k<<].s+t[k<<|].s-;
}
void pushdown(int k)
{
int tmp=t[k].tag;t[k].tag=-;
if(tmp==-||t[k].l==t[k].r)return;
t[k<<].s=t[k<<|].s=;
t[k<<].tag=t[k<<|].tag=tmp;
t[k<<].lc=t[k<<].rc=tmp;
t[k<<|].lc=t[k<<|].rc=tmp;
}
void change(int k,int x,int y,int c)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&r==y)
{t[k].lc=t[k].rc=c;t[k].s=;t[k].tag=c;return;}
int mid=(l+r)>>;
if(mid>=y)change(k<<,x,y,c);
else if(mid<x)change(k<<|,x,y,c);
else
{
change(k<<,x,mid,c);
change(k<<|,mid+,y,c);
}
pushup(k);
}
int ask(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&r==y)return t[k].s;
int mid=(l+r)>>;
if(mid>=y)return ask(k<<,x,y);
else if(mid<x)return ask(k<<|,x,y);
else
{
int tmp=;
if(t[k<<].rc^t[k<<|].lc)tmp=;
return ask(k<<,x,mid)+ask(k<<|,mid+,y)-tmp;
}
}
int getc(int k,int x)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==r)return t[k].lc;
int mid=(l+r)>>;
if(x<=mid)return getc(k<<,x);
else return getc(k<<|,x);
}
int solvesum(int x,int f)
{
int sum=;
while(belong[x]!=belong[f])
{
sum+=ask(,pl[belong[x]],pl[x]);
if(getc(,pl[belong[x]])==getc(,pl[ft[belong[x]][]]))sum--;
x=ft[belong[x]][];
}
sum+=ask(,pl[f],pl[x]);
return sum;
}
void solvechange(int x,int f,int c)
{
while(belong[x]!=belong[f])
{
change(,pl[belong[x]],pl[x],c);
x=ft[belong[x]][];
}
change(,pl[f],pl[x],c);
}
void solve()
{
int a,b,c;
dfs1();
dfs2(,);
build(,,n);
for(int i=;i<=n;i++)
change(,pl[i],pl[i],v[i]);
for(int i=;i<=m;i++)
{
char ch[];
scanf("%s",ch);
if(ch[]=='Q')
{
scanf("%d%d",&a,&b);
int t=lca(a,b);
printf("%d\n",solvesum(a,t)+solvesum(b,t)-);
}
else
{
scanf("%d%d%d",&a,&b,&c);
int t=lca(a,b);
solvechange(a,t,c);solvechange(b,t,c);
}
}
}
void ini()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&v[i]);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
insert(x,y);
}
}
int main()
{
ini();
solve();
return ;
}
3.【bzoj1984】月下“毛景树”
Change k w：将第k条树枝上毛毛果的个数改变为w个。
Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。
Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100001
#define inf 0x7fffffff
using namespace std;
int n,cnt=,sz;
int head[N],deep[N],size[N],pos[N],belong[N];
int fa[N][],id[N];
struct edge{int to,next,v;}e[N<<];
struct seg{int l,r,mx,a,c;}t[N<<];
void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];e[cnt].v=w;head[v]=cnt;
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if(t&(<<i))x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
{x=fa[x][i];y=fa[y][i];}
if(x==y)return x;
return fa[x][];
}
void pushdown(int k)
{
if(t[k].l==t[k].r)return;
if(t[k].c!=-)
{
t[k<<].a=t[k<<|].a=;
t[k<<].c=t[k<<|].c=t[k].c;
t[k<<].mx=t[k<<|].mx=t[k].c;
t[k].c=-;
}
if(t[k].a)
{
t[k<<].mx+=t[k].a;t[k<<|].mx+=t[k].a;
if(t[k<<].c!=-)t[k<<].c+=t[k].a;
else t[k<<].a+=t[k].a;
if(t[k<<|].c!=-)t[k<<|].c+=t[k].a;
else t[k<<|].a+=t[k].a;
t[k].a=;
}
}
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].c=-;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void pushup(int k)
{t[k].mx=max(t[k<<].mx,t[k<<|].mx);}
void change(int k,int x,int y,int v)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r){t[k].mx=t[k].c=v;return;}
int mid=(l+r)>>;
if(mid>=y)change(k<<,x,y,v);
else if(mid<x)change(k<<|,x,y,v);
else
{
change(k<<,x,mid,v);
change(k<<|,mid+,y,v);
}
pushup(k);
}
void add(int k,int x,int y,int v)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r){t[k].mx+=v;t[k].a=v;return;}
int mid=(l+r)>>;
if(mid>=y)add(k<<,x,y,v);
else if(mid<x)add(k<<|,x,y,v);
else
{
add(k<<,x,mid,v);
add(k<<|,mid+,y,v);
}
pushup(k);
}
int ask(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r)return t[k].mx;
int mid=(l+r)>>;
if(mid>=y)return ask(k<<,x,y);
else if(mid<x)return ask(k<<|,x,y);
else return max(ask(k<<,x,mid),ask(k<<|,mid+,y));
}
void solvechange(int x,int f,int v)
{
while(belong[x]!=belong[f])
{
change(,pos[belong[x]],pos[x],v);
x=fa[belong[x]][];
}
if(pos[f]+<=pos[x])
change(,pos[f]+,pos[x],v);
}
void solveadd(int x,int f,int v)
{
while(belong[x]!=belong[f])
{
add(,pos[belong[x]],pos[x],v);
x=fa[belong[x]][];
}
if(pos[f]+<=pos[x])
add(,pos[f]+,pos[x],v);
}
int solveask(int x,int f)
{
int mx=-inf;
while(belong[x]!=belong[f])
{
mx=max(mx,ask(,pos[belong[x]],pos[x]));
x=fa[belong[x]][];
}
if(pos[f]+<=pos[x])
mx=max(mx,ask(,pos[f]+,pos[x]));
return mx;
}
void solve()
{
char s[];
int u,v,w,f;
while()
{
scanf("%s",s);
switch(s[])
{
case 't':return;break;
case 'd':scanf("%d%d%d",&u,&v,&w);f=lca(u,v);
solveadd(u,f,w);solveadd(v,f,w);break;
case 'o':scanf("%d%d%d",&u,&v,&w);f=lca(u,v);
solvechange(u,f,w);solvechange(v,f,w);
break;
case 'h':scanf("%d%d",&u,&w);change(,pos[id[u]],pos[id[u]],w);break;
case 'a':scanf("%d%d",&u,&v);f=lca(u,v);
printf("%d\n",max(solveask(u,f),solveask(v,f)));
break;
}
}
}
void dfs1(int x,int f)
{
size[x]=;
for(int i=;i<=;i++)
if((<<i)<=deep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==f)continue;
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs1(e[i].to,x);
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int chain)
{
belong[x]=chain;
pos[x]=++sz;
int k=;
for(int i=head[x];i;i=e[i].next)
{
if(deep[x]<deep[e[i].to])
{
if(size[e[i].to]>size[k])k=e[i].to;
}
else {id[i>>]=x;add(,pos[x],pos[x],e[i].v);}
}
if(!k)return;
dfs2(k,chain);
for(int i=head[x];i;i=e[i].next)
if(deep[x]<deep[e[i].to]&&k!=e[i].to)
dfs2(e[i].to,e[i].to);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n-;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
build(,,n);
dfs1(,);
dfs2(,);
solve();
return ;
}
4.【bzoj3531】[Sdoi2014]旅行
S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。
”CC x c”：城市x的居民全体改信了c教；
”CW x w”：城市x的评级调整为w;
”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 10000005
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,cnt,place,size;
int s[];
int w[],c[],root[];
int fa[][],deep[],pl[],belong[],son[];
int ls[M],rs[M],mx[M],sum[M];
bool vis[];
struct data{int to,next;}e[];int head[];
void ins(int u,int v)
{
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
//==========================================================
void dfs1(int x)
{
vis[x]=;son[x]=;
for(int i=;i<=;i++)
if(s[i]<=deep[x])fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs1(e[i].to);
son[x]+=son[e[i].to];
}
}
void dfs2(int x,int chain)
{
place++;pl[x]=place;belong[x]=chain;
int k=;
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k])
k=e[i].to;
if(k)dfs2(k,chain);
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&e[i].to!=k)
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if(s[i]&t)x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return x;
return fa[x][];
}
//===========================================================预处理
void update(int x)
{
mx[x]=max(mx[ls[x]],mx[rs[x]]);
sum[x]=sum[ls[x]]+sum[rs[x]];
}
void change(int &k,int l,int r,int x,int num)
{
if(!k)k=++size;
if(l==r){mx[k]=sum[k]=num;return;}
int mid=(l+r)>>;
if(x<=mid)change(ls[k],l,mid,x,num);
else change(rs[k],mid+,r,x,num);
update(k);
}
int askmx(int k,int l,int r,int x,int y)
{
if(!k)return ;
if(l==x&&y==r)return mx[k];
int mid=(l+r)>>;
if(y<=mid)return askmx(ls[k],l,mid,x,y);
else if(x>mid)return askmx(rs[k],mid+,r,x,y);
else return max(askmx(ls[k],l,mid,x,mid),askmx(rs[k],mid+,r,mid+,y));
}
int asksum(int k,int l,int r,int x,int y)
{
if(!k)return ;
if(l==x&&y==r)return sum[k];
int mid=(l+r)>>;
if(y<=mid)return asksum(ls[k],l,mid,x,y);
else if(x>mid)return asksum(rs[k],mid+,r,x,y);
else return asksum(ls[k],l,mid,x,mid)+asksum(rs[k],mid+,r,mid+,y);
}
//===========================================================线段树
int solvemx(int c,int x,int f)
{
int mx=;
while(belong[x]!=belong[f])
{
mx=max(mx,askmx(root[c],,n,pl[belong[x]],pl[x]));
x=fa[belong[x]][];
}
mx=max(mx,askmx(root[c],,n,pl[f],pl[x]));
return mx;
}
int solvesum(int c,int x,int f)
{
int sum=;
while(belong[x]!=belong[f])
{
sum+=asksum(root[c],,n,pl[belong[x]],pl[x]);
x=fa[belong[x]][];
}
sum+=asksum(root[c],,n,pl[f],pl[x]);
return sum;
}
//===========================================================树链剖分
int main()
{
s[]=;for(int i=;i<=;i++)s[i]=(s[i-]<<);
n=read();m=read();
for(int i=;i<=n;i++)
w[i]=read(),c[i]=read();
for(int i=;i<n;i++)
{
int u=read(),v=read();
ins(u,v);
}
dfs1();dfs2(,);
for(int i=;i<=n;i++)
change(root[c[i]],,n,pl[i],w[i]);
for(int i=;i<=m;i++)
{
char ch[];scanf("%s",ch);
int x=read(),y=read();
if(ch[]=='C')
{
if(ch[]=='C')
{
change(root[c[x]],,n,pl[x],);
c[x]=y;
change(root[c[x]],,n,pl[x],w[x]);
}
else {change(root[c[x]],,n,pl[x],y);w[x]=y;}
}
else
{
int f=lca(x,y);
if(ch[]=='S')
{
int t=solvesum(c[x],x,f)+solvesum(c[x],y,f);
if(c[x]==c[f])t-=w[f];
printf("%d\n",t);
}
else
printf("%d\n",max(solvemx(c[x],x,f),solvemx(c[x],y,f)));
}
}
return ;
}
5.【bzoj1036】[ZJOI2008]树的统计Count
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define N 30005
#define M 60005
using namespace std;
int n,q,cnt,sz;
int fa[N][],v[N],deep[N],size[N],head[N];
int pos[N],belong[N];
bool vis[N];
struct data{int to,next;}e[M];
struct seg{int l,r,mx,sum;}t[];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void ini()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
insert(x,y);
}
for(int i=;i<=n;i++)scanf("%d",&v[i]);
}
void dfs1(int x)
{
size[x]=;vis[x]=;
for(int i=;i<=;i++)
{
if(deep[x]<(<<i))break;
fa[x][i]=fa[fa[x][i-]][i-];//倍增处理祖先信息
}
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs1(e[i].to);
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int chain)
{
int k=;sz++;
pos[x]=sz;//分配x结点在线段树中的编号
belong[x]=chain;
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&size[e[i].to]>size[k])
k=e[i].to;//选择子树最大的儿子继承重链
if(k==)return;
dfs2(k,chain);
for(int i=head[x];i;i=e[i].next)
if(deep[e[i].to]>deep[x]&&k!=e[i].to)
dfs2(e[i].to,e[i].to);//其余儿子新开重链
}
int lca(int x,int y)//求lca
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if(t&(<<i))x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
{x=fa[x][i];y=fa[y][i];}
if(x==y)return x;
else return fa[x][];
}
void build(int k,int l,int r)//建线段树
{
t[k].l=l;t[k].r=r;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
void change(int k,int x,int y)//线段树单点修改
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==r){t[k].sum=t[k].mx=y;return;}
if(x<=mid)change(k<<,x,y);
else change(k<<|,x,y);
t[k].sum=t[k<<].sum+t[k<<|].sum;
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
int querysum(int k,int x,int y)//线段树区间求和
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&y==r)return t[k].sum;
if(y<=mid)return querysum(k<<,x,y);
else if(x>mid)return querysum(k<<|,x,y);
else {return querysum(k<<,x,mid)+querysum(k<<|,mid+,y);}
}
int querymx(int k,int x,int y)//线段树区间求最大值
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&y==r)return t[k].mx;
if(y<=mid)return querymx(k<<,x,y);
else if(x>mid)return querymx(k<<|,x,y);
else {return max(querymx(k<<,x,mid),querymx(k<<|,mid+,y));}
}
int solvesum(int x,int f)
{
int sum=;
while(belong[x]!=belong[f])//不在一条重链上就将x跳到链首，走一条轻边，如此反复
{
sum+=querysum(,pos[belong[x]],pos[x]);
x=fa[belong[x]][];
}
sum+=querysum(,pos[f],pos[x]);
return sum;
}
int solvemx(int x,int f)
{
int mx=-inf;
while(belong[x]!=belong[f])
{
mx=max(mx,querymx(,pos[belong[x]],pos[x]));
x=fa[belong[x]][];
}
mx=max(mx,querymx(,pos[f],pos[x]));
return mx;
}
void solve()
{
build(,,n);
for(int i=;i<=n;i++)
change(,pos[i],v[i]);
scanf("%d",&q);char ch[];
for(int i=;i<=q;i++)
{
int x,y;scanf("%s%d%d",ch,&x,&y);
if(ch[]=='C'){v[x]=y;change(,pos[x],y);}
else
{
int t=lca(x,y);
if(ch[]=='M')
printf("%d\n",max(solvemx(x,t),solvemx(y,t)));
else
printf("%d\n",solvesum(x,t)+solvesum(y,t)-v[t]);
}
}
}
int main()
{
ini();
dfs1();
dfs2(,);
solve();
return ;
}
6.【poj3237】Tree
CHANGE i v 改变第i条边的权值为v
NEGATE a b a-b的边权值取反
QUERY a b 查询a-b的最大权值
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int bin[];
int T,n,cnt,P;
int last[];
int bl[],pos[],to[];
int fa[][],size[],deep[];
struct edge{
int to,next,v;
}e[];
struct seg{
int l,r,mn,mx,tag;
}t[];
void solve(int &x,int &y)
{
int t=x;x=-y;y=-t;
}
void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void update(int k)
{
t[k].mn=min(t[k<<].mn,t[k<<|].mn);
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
void pushdown(int k)
{
int l=t[k].l,r=t[k].r;
if(l==r||!t[k].tag)return;t[k].tag=;
t[k<<].tag^=;t[k<<|].tag^=;
solve(t[k<<].mn,t[k<<].mx);
solve(t[k<<|].mn,t[k<<|].mx);
}
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].tag=;
t[k].mn=inf;t[k].mx=-inf;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void change(int k,int x,int val)
{
pushdown(k);
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==r)
{
t[k].mn=t[k].mx=val;return;
}
if(x<=mid)change(k<<,x,val);
else change(k<<|,x,val);
update(k);
}
void rever(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y)
{
solve(t[k].mn,t[k].mx);
t[k].tag=;return;
}
if(y<=mid)rever(k<<,x,y);
else if(x>mid)rever(k<<|,x,y);
else rever(k<<,x,mid), rever(k<<|,mid+,y);
update(k);
}
int query(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(x==l&&y==r)return t[k].mx;
if(y<=mid)return query(k<<,x,y);
else if(x>mid)return query(k<<|,x,y);
else return max(query(k<<,x,mid),query(k<<|,mid+,y));
}
void dfs1(int x)
{
size[x]=;
for(int i=;i<=;i++)
if(bin[i]<=deep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x][])
{
deep[e[i].to]=deep[x]+;
fa[e[i].to][]=x;
dfs1(e[i].to);
size[x]+=size[e[i].to];
}
}
void dfs2(int x,int chain)
{
bl[x]=chain;pos[x]=++P;
int k=;
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x][])
{
if(size[e[i].to]>size[k])k=e[i].to;
}
else
{
to[i>>]=pos[x];change(,pos[x],e[i].v);
}
if(!k)return;
dfs2(k,chain);
for(int i=last[x];i;i=e[i].next)
if(e[i].to!=fa[x][]&&e[i].to!=k)
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=;i<=;i++)
if(t&bin[i])x=fa[x][i];
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return x;
return fa[x][];
}
int solvequery(int x,int f)
{
int mx=-inf;
while(bl[x]!=bl[f])
{
mx=max(mx,query(,pos[bl[x]],pos[x]));
x=fa[bl[x]][];
}
if(pos[f]+<=pos[x])
mx=max(mx,query(,pos[f]+,pos[x]));
return mx;
}
void solverever(int x,int f)
{
while(bl[x]!=bl[f])
{
rever(,pos[bl[x]],pos[x]);
x=fa[bl[x]][];
}
if(pos[f]+<=pos[x])
rever(,pos[f]+,pos[x]);
}
int main()
{
bin[]=;for(int i=;i<;i++)bin[i]=bin[i-]<<;
T=read();
while(T--)
{
P=;cnt=;
memset(last,,sizeof(last));
memset(deep,,sizeof(deep));
memset(fa,,sizeof(fa));
n=read();
for(int i=;i<n;i++)
{
int u=read(),v=read(),w=read();
insert(u,v,w);
}
build(,,n);
dfs1();
dfs2(,);
char ch[];
while(scanf("%s",ch+))
{
if(ch[]=='D')break;
int x=read(),y=read();
if(ch[]=='Q')
{
int f=lca(x,y);
printf("%d\n",max(solvequery(x,f),solvequery(y,f)));
}
if(ch[]=='C')
change(,to[x],y);
if(ch[]=='N')
{
int f=lca(x,y);
solverever(x,f);solverever(y,f);
}
}
}
return ;
}
7.Codeforces 343D Water Tree
（1）“1 v"，表示将以点v为根节点的子树全部赋值为1，
（2）"2 v"，表示将点v以及点v的所有祖先节点全部赋值为0，
（3）"3 v"，表示查询点v的值。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std; #define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1)) const int N=; struct Edge
{
int v,pre;
Edge(){}
Edge(int v,int pre) :
v(v),pre(pre) {}
}edge[N*]; int n,m;
int head[N],nEdge;
int low[N],high[N],idx; void edgeInit()
{
nEdge=;
memset(head,-,sizeof(head));
}
void addEdge(int u,int v)
{
edge[nEdge]=Edge(v,head[u]);
head[u]=nEdge++;
} void dfs(int u,int pre)
{
low[u]=++idx;
for(int i=head[u];i!=-;i=edge[i].pre)
{
int v=edge[i].v;
if(v==pre) continue;
dfs(v,u);
}
high[u]=idx;
} struct Segtree
{
int delay[N*],mx[N*]; void fun(int ind,int valu){ mx[ind]=delay[ind]=valu; }
void PushDown(int ind)
{
if(delay[ind])
{
fun(LL(ind),delay[ind]);
fun(RR(ind),delay[ind]);
delay[ind]=;
}
}
void PushUp(int ind)
{
mx[ind]=max(mx[LL(ind)],mx[RR(ind)]);
}
void build(int lft,int rht,int ind)
{
delay[ind]=;
if(lft!=rht)
{
int mid=MID(lft,rht);
build(lft,mid,LL(ind));
build(mid+,rht,RR(ind));
}
}
void updata(int st,int ed,int valu,int lft,int rht,int ind)
{
if(st<=lft&&rht<=ed) fun(ind,valu);
else
{
PushDown(ind);
int mid=MID(lft,rht);
if(st<=mid) updata(st,ed,valu,lft,mid,LL(ind));
if(ed> mid) updata(st,ed,valu,mid+,rht,RR(ind));
PushUp(ind);
}
}
int query(int st,int ed,int lft,int rht,int ind)
{
if(st<=lft&&rht<=ed) return mx[ind];
else
{
PushDown(ind);
int mid=MID(lft,rht);
int mx1=,mx2=;
if(st<=mid) mx1=query(st,ed,lft,mid,LL(ind));
if(ed> mid) mx2=query(st,ed,mid+,rht,RR(ind));
PushUp(ind);
return max(mx1,mx2);
}
}
}seg1,seg2; int main()
{
while(scanf("%d",&n)!=EOF)
{
edgeInit(); idx=;
for(int i=;i<n;i++)
{
int a,b; scanf("%d%d",&a,&b);
addEdge(a,b); addEdge(b,a);
} dfs(,-); seg1.build(,idx,); seg2.build(,idx,); scanf("%d",&m);
for(int i=;i<=m;i++)
{
int a,u; scanf("%d%d",&a,&u);
if(a==) seg1.updata(low[u],high[u],i,,idx,);
else if(a==) seg2.updata(low[u],low[u],i,,idx,);
else
{
int tmp1=seg1.query(low[u],low[u],,idx,);
int tmp2=seg2.query(low[u],high[u],,idx,);
if(tmp1>tmp2) puts("");
else puts("");
}
}
}
return ;
}