题解 P2590 【[ZJOI2008]树的统计】

Treaker · 2019-09-18 20:23:59 · 题解

一个树剖题。

我们可以对于线段树的每一个节点，维护一下他的总和 与 最大值 即可

还是比较裸的（一眼树剖全是板子）

这里采用数组写法，指针写法详见我博客其他树剖题。

顺便推荐做一下模板【模板】树链剖分

完整代码如下：

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 30030;
int ls(int x) {return x << 1;}
int rs(int x) {return x << 1 | 1;}
int n , m , cnt;
int head[N] , dep[N] , dfn[N] , id[N] , hs[N] , fa[N] , top[N] , w[N] , sum[N << 2] , maxn[N << 2] , size[N];
char s[10];
struct Edge // 链式前向星
{
    int to , nxt;
}e[N << 1];
void add(int from,int to) // 加边
{
    e[++cnt] = (Edge){to,head[from]};
    head[from] = cnt;
}
void get_tree(int now) //建树
{
    size[now] = 1;
    for(int i = head[now] , to;i;i = e[i].nxt)
    {
        to = e[i].to;
        if(dep[to]) continue;
        fa[to] = now;
        dep[to] = dep[now] + 1;
        get_tree(to);
        size[now] += size[to];
        if(size[to] > size[hs[now]])    hs[now] = to;
    }
}
void dfs(int now,int topfa)
{
    dfn[now] = ++cnt;
    id[cnt] = now;
    top[now] = topfa;
    if(hs[now]) dfs(hs[now],topfa);
    for(int i = head[now] , to;i;i = e[i].nxt)
    {
        to = e[i].to;
        if(to == fa[now] || to == hs[now])  continue;
        dfs(to,to);
    }
}
void build(int p,int l,int r)
{
    if(l == r)
    {
        maxn[p] = sum[p] = w[id[l]];
        return ; 
    }
    int mid = (l + r) >> 1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    sum[p] = sum[ls(p)] + sum[rs(p)];
    maxn[p] = max(maxn[ls(p)],maxn[rs(p)]);
}
void chenge(int p,int l,int r,int x,int k)
{
    if(l == r)  
    {
        sum[p] = k;
        maxn[p] = k;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)    chenge(ls(p),l,mid,x,k);
    else    chenge(rs(p),mid+1,r,x,k);
    sum[p] = sum[ls(p)] + sum[rs(p)];
    maxn[p] = max(maxn[ls(p)],maxn[rs(p)]);
}
int query_sum(int p,int l,int r,int x,int y)
{
    if(x <= l && r <= y)    return sum[p];
    int res = 0;
    int mid = (l + r) >> 1;
    if(x <= mid)    res = res + query_sum(ls(p),l,mid,x,y);
    if(y > mid)     res = res + query_sum(rs(p),mid+1,r,x,y);
    return res;
}
int query_max(int p,int l,int r,int x,int y)
{
    if(x <= l && r <= y)    return maxn[p];
    int res = -2147483647;
    int mid = (l + r) >> 1;
    if(x <= mid)    res = max(res,query_max(ls(p),l,mid,x,y));
    if(y > mid)     res = max(res,query_max(rs(p),mid+1,r,x,y));
    return res;
}
int slove1(int x,int y)
{
    int res = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        res = res + query_sum(1,1,n,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x,y);
    res = res + query_sum(1,1,n,dfn[y],dfn[x]);
    return res;
}
int slove2(int x,int y)
{
    int res = -2147483647;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])   swap(x,y);
        res = max(res , query_max(1,1,n,dfn[top[x]],dfn[x]));
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x,y);
    res = max(res , query_max(1,1,n,dfn[y],dfn[x]));
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 , a , b;i < n;i ++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    for(int i = 1;i <= n;i ++)  scanf("%d",&w[i]);
    cnt = 0;
    dep[1] = 1;
    get_tree(1);
    dfs(1,1);
    build(1,1,n);
    scanf("%d",&m);
    for(int i = 1 , u , v;i <= m;i ++)
    {
        scanf("%s%d%d",s,&u,&v);
        if(s[1] == 'H') chenge(1,1,n,dfn[u],v);
        else    if(s[1] == 'S') printf("%d\n",slove1(u,v));
        else    printf("%d\n",slove2(u,v));
    }
    return 0;
}