洛谷P2590[ZJOI2008]树的统计

题目描述

一棵树上有\(n\)个节点，编号分别为\(1\)到\(n\)，每个节点都有一个权值\(w\)。

我们将以下面的形式来要求你对这棵树完成一些操作：

\(I\). \(CHANGE\) \(u\) \(t\) : 把结点\(u\)的权值改为\(t\)

\(II\). \(QMAX\) \(u\) \(v\): 询问从点\(u\)到点\(v\)的路径上的节点的最大权值

\(III\). \(QSUM\) \(u\) \(v\): 询问从点\(u\)到点\(v\)的路径上的节点的权值和

注意：从点\(u\)到点\(v\)的路径上的节点包括\(u\)和\(v\)本身

输入输出格式

输入格式：

输入文件的第一行为一个整数\(n\)，表示节点的个数。

接下来\(n – 1\)行，每行\(2\)个整数\(a\)和\(b\)，表示节点\(a\)和节点\(b\)之间有一条边相连。

接下来一行\(n\)个整数，第i个整数\(w_i\)表示节点i的权值。

接下来\(1\)行，为一个整数\(q\)，表示操作的总数。

接下来\(q\)行，每行一个操作，以“\(CHANGE\) \(u\) \(t\)”或者“\(QMAX\) \(u\) \(v\)”或者“\(QSUM\) \(u\) \(v\)”的形式给出。

输出格式：

对于每个“\(QMAX\)”或者“\(QSUM\)”的操作，每行输出一个整数表示要求输出的结果。

输入输出样例

输入样例#1：

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

输出样例#1：

4
1
2
2
10
6
5
6
5
16

说明

对于\(100\%\)的数据，保证\(1 \leq n \leq 30000，0 \leq q \leq 200000\)；中途操作中保证每个节点的权值\(w\)在\(-30000\)到\(30000\)之间。

思路：这道题目跟洛谷\(P3384\)那道题的区别在于那道题是区间修改，这道题是单点修改，这道题还多了查询任意两点最短路径上的最大点权，实际上区间修改包括单点修改，所以这道题只多用树剖维护一个路径最大点权即可。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 30007
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
int head[maxn],d[maxn],lazy[maxn<<2],sum[maxn<<2];
int maxx[maxn<<2],a[maxn],num,cnt,n,m,fa[maxn],id[maxn];
int w[maxn],top[maxn],size[maxn],son[maxn];
char s[8];
struct node {
  int v,nxt;
}e[maxn<<1];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
inline void pushup(int rt) {
  sum[rt]=sum[ls]+sum[rs];
  maxx[rt]=max(maxx[ls],maxx[rs]);
}
void build(int rt, int l, int r) {
  if(l==r) {
    sum[rt]=a[l];
    maxx[rt]=a[l];
    return;
  }
  int mid=(l+r)>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(rt);
}
void add(int rt, int l, int r, int L, int val) {
  if(l==r) {
    sum[rt]=maxx[rt]=val;
    return;
  }
  int mid=(l+r)>>1;
  if(L>mid) add(rs,mid+1,r,L,val);
  else add(ls,l,mid,L,val);
  pushup(rt);
}
int csum(int rt, int l, int r, int L, int R) {
  if(L>r||R<l) return 0;
  if(L<=l&&r<=R) return sum[rt];
  int mid=(l+r)>>1;
  return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R);
}
int cmax(int rt, int l, int r, int L, int R) {
  int ans=-1020040222;
  if(L>r||R<l) return 0;
  if(L<=l&&r<=R) return maxx[rt];
  int mid=(l+r)>>1;
  if(L<=mid) ans=max(ans,cmax(ls,l,mid,L,R));
  if(R>mid) ans=max(ans,cmax(rs,mid+1,r,L,R));
  return ans;
}
void dfs1(int u, int f) {
  size[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(v!=f) {
      d[v]=d[u]+1;
      fa[v]=u;
      dfs1(v,u);
      size[u]+=size[v];
      if(size[v]>size[son[u]]) son[u]=v;    
    }
  }
}
void dfs2(int u, int t) {
  id[u]=++cnt;
  a[cnt]=w[u];
  top[u]=t;
  if(son[u]) dfs2(son[u],t);
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
  }
}
int calc1(int x, int y) {
  int maxx=-1020040222;
  int fx=top[x],fy=top[y];
  while(fx!=fy) {
    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);
    maxx=max(maxx,cmax(1,1,cnt,id[fx],id[x]));
    x=fa[fx],fx=top[x];
  }
  if(id[x]>id[y]) swap(x,y);
  maxx=max(maxx,cmax(1,1,cnt,id[x],id[y]));
  return maxx;
}
int calc2(int x, int y) {
  int ans=0;
  int fx=top[x],fy=top[y];
  while(fx!=fy) {
    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);
    ans+=csum(1,1,cnt,id[fx],id[x]);
    x=fa[fx],fx=top[x];
  }
  if(id[x]>id[y]) swap(x,y);
  ans+=csum(1,1,cnt,id[x],id[y]);
  return ans;
}
int main() {
  scanf("%d",&n);
  for(int i=1,u,v;i<n;++i) {
    scanf("%d%d",&u,&v);
    ct(u,v);ct(v,u);
  }
  for(int i=1;i<=n;++i) scanf("%d",&w[i]);
  d[1]=1,fa[1]=1;
  dfs1(1,0);dfs2(1,1);build(1,1,n);
  scanf("%d",&m);
  for(int i=1,x,y;i<=m;++i) {
    scanf("%s%d%d",s,&x,&y);
    if(s[1]=='H') add(1,1,n,id[x],y);
    if(s[1]=='M') printf("%d\n",calc1(x,y));
    if(s[1]=='S') printf("%d\n",calc2(x,y));
  }
  return 0;
}