洛谷 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本身

我们可以将树大约划分为\(\sqrt{n}\)块，每个块内维护到块内根节点的路径长度以及点权最大值，而且，显然，我们可以通过寻找它们的\(LCA\)来找到他们路径上的有关信息，而这里我们已经对树进行了分块。

所以在同一个块内的暴跳时间复杂度最坏为\(O(\sqrt{n})\)

在块与块之间的暴跳的时间复杂度最坏为\(O(\sqrt{n})\)

轻松AC本题目

代码中有较详细注释，贴代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct cc{
    int to,nex;
}e[maxn],dis[maxn];
int head[maxn],cnt1,h[maxn],cnt2;
void add1(int u,int v)//原树边 
{
    ++cnt1;
    e[cnt1].to=v;
    e[cnt1].nex=head[u];
    head[u]=cnt1;
}
void add2(int u,int v)//分块后块内树边 
{
    ++cnt2;
    dis[cnt2].to=v;
    dis[cnt2].nex=h[u];
    h[u]=cnt2;
}
int rt[maxn],mx[maxn],sum[maxn],siz[maxn];
int n,m,v[maxn],deep[maxn],len,fa[maxn];
void dfs(int u,int f,int dep)
{
    deep[u]=dep;
    int tmp=rt[u];
    fa[u]=f;
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].to;
        if(v!=f)
        {
            if(siz[tmp]+1<len)
            {
                add2(u,v);//块内树连边 
                rt[v]=tmp;
                ++siz[tmp];
            }
            dfs(v,u,dep+1);
        }
    }
}
void build(int u,int num,int vmx)//维护当前节点，到块内根节点的和，最大值
{
    num+=v[u],sum[u]=num;
    vmx=max(vmx,v[u]),mx[u]=vmx;
    for(int i=h[u];i;i=dis[i].nex)
        build(dis[i].to,num,vmx);
} 
int query(int a,int b,int tag)
{
    int ans1=0;//QSUM
    int ans2=-(1<<30);//QMAX
    while(a!=b)//类似于倍增，只不过这里的距离为sqrt(n) 
    {
        if(deep[a]<deep[b]) swap(a,b);
        if(rt[a]==rt[b])//若所属同一个块
        {
            ans1+=v[a];
            ans2=max(ans2,v[a]);
            a=fa[a];//由于在同一块内，暴力跳的复杂度只为O(sqrt(n)) 
        } 
        else
        {
            if(deep[rt[a]]<deep[rt[b]]) swap(a,b);//块的深度更深 
            ans1+=sum[a];
            ans2=max(ans2,mx[a]);
            a=fa[rt[a]];//直接跳一个块 
        }
    }
    ans1+=v[a];
    ans2=max(ans2,v[a]);//更新它们的LCA的值 
    if(tag==0) return ans2;
    else return ans1; 
} 
void change(int u,int x)
{
    v[u]=x;
    if(u==rt[u]) build(u,0,-(1<<30));//如果是块内根节点就整个块更新
    else build(u,sum[fa[u]],mx[fa[u]]);//如果不是，就从其父亲开始更新
}
int main()
{
    int x,y;
    scanf("%d",&n);
    len=sqrt(n);
    for(int i=1;i<n;++i)
        scanf("%d%d",&x,&y),add1(x,y),add1(y,x);//原树边 
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]),rt[i]=i;
    dfs(1,0,0);
    for(int i=1;i<=n;++i)
        if(rt[i]==i) 
            build(i,0,-(1<<30));
    scanf("%d",&m);
    char opt[30];
    for(int i=1;i<=m;++i)
    {
        scanf("%s%d%d",opt,&x,&y);
        if(opt[1]=='M')//QMAX
            printf("%d\n",query(x,y,0));//01维护询问问题 
        else if(opt[1]=='S')//QSUM
            printf("%d\n",query(x,y,1));//01维护询问问题 
        else //CHANGE 
            change(x,y);
    }
    return 0;
}

骗分过样例，暴力出奇迹！！！

洛谷 P2590 [ZJOI2008]树的统计

原文：https://www.cnblogs.com/HenryHuang-Never-Settle/p/10786200.html