Housewife Wind

Housewife Wind

参考博客：POJ2763 Housewife Wind(树剖+线段树)

差不多是直接套线段树+树剖的板子，但是也有一些需要注意的地方

建树：

void build()

{

    for( int i=1;i<n;++i)

    {

        if(dep[e[i][1]]<dep[e[i][0]]) swap(e[i][1],e[i][0]);

        update(id[e[i][1]],1,n-1,e[i][2],1);

    }

}

单点更新（令某个点为 k，而不是加 k）：

void update(int x,int s,int t,int k,int p)

{

    if(s==t)

    {

        d[p]=k;return ;

    }

    int m=(s+t)>>1;

    if(x<=m) update(x,s,m,k,lson);

    else update(x,m+1,t,k,rson);

    d[p]=d[lson]+d[rson];

}

线段树区间求和：

int getsum(int l,int r,int s,int t,int p)

{

    if(l>r) return 0;        //记得加上这个，不然会re

    if(l<=s&&t<=r) return d[p];

    int m=(s+t)>>1;

    ll sum=0;

    if(l<=m) sum+=getsum(l,r,s,m,lson);

    if(r>m) sum+=getsum(l,r,m+1,t,rson);

    return sum;

}

树剖区间求和：

int query(int x,int y)

{

    ll ans=0;

    if(x==y) return 0;

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ans+=getsum(id[top[x]],id[x],1,n-1,1);

        x=f[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    ans+=getsum(id[son[x]],id[y],1,n-1,1);    //要记住是son[x]的id到y的id

    return ans;

}

代码：

// Created by CAD on 2019/8/13.

#include <algorithm>

#include <cstdio>

#define lson (p<<1)

#define rson ((p<<1)|1)

using namespace std;

#define ll long long

const int maxn=2e5+5;

int dep[maxn],top[maxn],son[maxn],f[maxn],siz[maxn],tot;

int id[maxn],cnt,head[maxn],nxt[maxn],to[maxn];

int d[maxn<<1],n,e[maxn][3];

inline int read() {

    int x = 0, w = 1;

    char ch = 0;

    while (ch < '0' || ch > '9') {

        if (ch == '-') w = -1;

        ch = getchar();

    }

    while (ch >= '0' && ch <= '9') {

        x = x * 10 + (ch - '0');

        ch = getchar();

    }

    return x * w;

}

inline void write(int x) {

    static int sta[35];

    int top = 0;

    do {

        sta[top++] = x % 10, x /= 10;

    } while (x);

    while (top) putchar(sta[--top] + 48);

    putchar('\n');

}

void add(int u,int v)

{

    nxt[++cnt]=head[u];

    head[u]=cnt;

    to[cnt]=v;

}

void dfs1(int u,int fa)

{

    f[u]=fa;dep[u]=dep[fa]+1;siz[u]=1;

    int maxson=-1;

    for( int i=head[u];i;i=nxt[i])

    {

        int v=to[i];if(v==fa) continue;

        dfs1(v,u);siz[u]+=siz[v];

        if(siz[v]>maxson) maxson=siz[v],son[u]=v;

    }

}

void dfs2(int u,int Top)

{

    top[u]=Top;id[u]=tot++;

    if(!son[u]) return ;

    dfs2(son[u],Top);

    for( int i=head[u];i;i=nxt[i])

    {

        int v=to[i];

        if(v==f[u]||v==son[u]) continue;

        dfs2(v,v);

    }

}

void update(int x,int s,int t,int k,int p)

{

    if(s==t)

    {

        d[p]=k;return ;

    }

    int m=(s+t)>>1;

    if(x<=m) update(x,s,m,k,lson);

    else update(x,m+1,t,k,rson);

    d[p]=d[lson]+d[rson];

}

int getsum(int l,int r,int s,int t,int p)

{

    if(l>r) return 0;

    if(l<=s&&t<=r) return d[p];

    int m=(s+t)>>1;

    ll sum=0;

    if(l<=m) sum+=getsum(l,r,s,m,lson);

    if(r>m) sum+=getsum(l,r,m+1,t,rson);

    return sum;

}

void build()

{

    for( int i=1;i<n;++i)

    {

        if(dep[e[i][1]]<dep[e[i][0]]) swap(e[i][1],e[i][0]);

        update(id[e[i][1]],1,n-1,e[i][2],1);

    }

}

int query(int x,int y)

{

    ll ans=0;

    if(x==y) return 0;

    while(top[x]!=top[y])

    {

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ans+=getsum(id[top[x]],id[x],1,n-1,1);

        x=f[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    ans+=getsum(id[son[x]],id[y],1,n-1,1);

    return ans;

}

int main()

{

    int p,s;

    n=read(),p=read(),s=read();

    cnt=1,tot=0;

    for( int i=1;i<n;++i)

    {

        e[i][0]=read(),e[i][1]=read(),e[i][2]=read();

        add(e[i][0],e[i][1]),add(e[i][1],e[i][0]);

    }

    dfs1(1,0);dfs2(1,1);

    build();

    for( int i=1;i<=p;++i)

    {

        int op,x,y;

        op=read();

        if(op==0)

            x=read(),write(query(x,s)),s=x;

        else x=read(),y=read(),update(id[e[x][1]],1,n-1,y,1);

    }

}

巴特西

Housewife Wind

最新文章

热门文章