Housewife Wind(树链剖分模板-边权区间查询)

题目链接:https://cn.vjudge.net/problem/POJ-2763

题目大意:一个树形图,一个人现在在s点,每条边有一个权值,有两种操作,一是将第x条边的边权变为d,二是查询s点到a点见的边权和。

解题思路:树链剖分区间查询模板题

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=1e5+55;
//存边
struct node
{
    int u,v,w;
}edge[maxn];
//前向星
struct edge
{
    int to,next;
}e[maxn<<1];
//建树
struct Tree
{
    int sum;
}tree[maxn<<2];

int head[maxn],data[maxn],id_data[maxn],fa[maxn],son[maxn],siz[maxn],deep[maxn],top[maxn],tid[maxn];
int cnt,idx;
int n,q,s;

void add(int u,int v)
{
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

void dfs(int u,int f,int d)
{
    siz[u]=1;
    deep[u]=d;
    fa[u]=f;
    son[u]=-1;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=f)
        {
            dfs(v,u,d+1);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[son[u]]<siz[v])
            {
                son[u]=v;
            }
        }
    }
}

void dfss(int u,int t)
{
    top[u]=t;
    tid[u]=++idx;
    if(son[u]!=-1)
    {
        dfss(son[u],t);
    }
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(son[u]!=v&&fa[u]!=v)
            dfss(v,v);
    }
}

void build(int o,int l,int r)
{
    if(l==r)
    {
        tree[o].sum=id_data[l];
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
}

//普通的线段树查询
int query(int l,int r,int ll,int rr,int o)
{
    if(l<=ll&&rr<=r)
        return tree[o].sum;
    int mid=(ll+rr)>>1;
    int ret=0;
    if(l<=mid)ret+=query(l,r,ll,mid,o<<1);
    if(r>mid)ret+=query(l,r,mid+1,rr,o<<1|1);
    return ret;
}

int getans(int u,int v)
{
    int ans=0;
    //向上爬
    while(top[u]!=top[v])
    {
        if(deep[top[u]]<deep[top[v]])
            swap(u,v);
        ans+=query(tid[top[u]],tid[u],1,n,1);
        u=fa[top[u]];
    }
    if(u==v)
        return ans;
    //在同一条链上的时候求和深度潜的节点的儿子到深度深的节点的和
    if(deep[u]>deep[v])swap(u,v);
    ans+=query(tid[son[u]],tid[v],1,n,1);
    return ans;
}

void pushup(int o)
{
    tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
}

void updata(int p,int v,int l,int r,int o)
{
    if(l==r)
    {
        tree[o].sum=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)updata(p,v,l,mid,o<<1);
    else updata(p,v,mid+1,r,o<<1|1);
    pushup(o);
}

int main()
{
    scanf("%d%d%d",&n,&q,&s);
    memset(head,-1,sizeof(head));
    cnt=0;
    //存边+前向星建图
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        add(edge[i].u,edge[i].v);
        add(edge[i].v,edge[i].u);
    }
    idx=0;
    //两遍dfs
    dfs(1,-1,1);
    dfss(1,1);
    //将边权写到深的节点里
    for(int i=1;i<n;i++)
    {
        if(deep[edge[i].u]<deep[edge[i].v])
        {
            swap(edge[i].u,edge[i].v);
        }
        id_data[tid[edge[i].u]]=edge[i].w;
    }
    //建树
    build(1,1,n);
    while(q--)
    {
        int d,a,b;
        scanf("%d",&d);
        if(d==0)
        {
            //区间查询
            scanf("%d",&a);
            printf("%d\n",getans(s,a));
            s=a;
        }
        else
        {
            //单点更新
            scanf("%d%d",&a,&b);
            updata(tid[edge[a].u],b,1,n,1);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注