POJ 2763 Housewife Wind 树链拋分

一、前言

　　这破题WA了一天，最后重构还是WA，最后通过POJ讨论版得到的数据显示，我看上去是把某个变量写错了。。于是，还是低级错误背锅啊。。。。代码能力有待进一步提升2333333

二、题意

　　某家庭主妇住在一棵树上，他的若干个孩子在树的若干个节点上有分布，主妇同学需要从某给定节点出发，飞到树上的制定节点，在过程中，边权可能会发生改变，问从当前节点到指定节点的边权和。

三、解法

　　树链拋分，点更新查区间。

// #include<bits/stdc++.h>

#include<iostream>

#include<math.h>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pp pair<int ,int>

const ll MAXN=1e5+;

class Node

{

    public:

        int next,to,cost;

        void init(int a,int b,int c)

        {

            this->next=a;

            this->to=b;

            this->cost=c;

        }

};

Node G[MAXN*];

int tree[MAXN],child[MAXN],deep[MAXN],number[MAXN],top[MAXN],points[MAXN],father[MAXN];

int size,summ,n,q,s;

void insert(int pos,int key)

{

    while(pos<MAXN)

    {

        tree[pos]+=key;

        pos+=pos&(-pos);

    }

}

int getSum(int pos)

{

    int ans=;

    while(pos)

    {

        ans+=tree[pos];

        pos-=pos&(-pos);

    }return ans;

}

void add(int from,int to,int cost)

{

    G[summ].init(points[from],to,cost);

    points[from]=summ++;

}

void dfs_1(int now,int last,int dep)

{

    deep[now]=dep;

    father[now]=last;

    child[now]=;

    for(int i=points[now];i!=-;i=G[i].next)

    {

        int tar=G[i].to;

        int cost=G[i].cost;

        if(tar==last)continue;

        dfs_1(tar,now,dep+);

        child[now]+=child[tar];

    }

}

void dfs(int now,int last,int first,int cc=)

{

    top[now] = first ? first : now;

    insert(size,cc);

     // cout<<"check_number: "<<now<<ends<<size<<endl;

    number[now]=size++;

    int maxx,pos,coS;

    maxx=pos=-;

    for(int i=points[now];i!=-;i=G[i].next)

    {

        int tar=G[i].to;

        int cost=G[i].cost;

        if(tar==last)continue;

        if(maxx<child[tar])

        {

            maxx=child[tar];

            pos=tar;

            coS=cost;

        }

    }if(pos!=-)dfs(pos,now,top[now],coS);

    for(int i=points[now];i!=-;i=G[i].next)

    {

        int tar=G[i].to;

        int cost=G[i].cost;

        if(tar==last||tar==pos)continue;

        dfs(tar,now,,cost);

    }

}

void update(int num,int key)

{

    int a=G[num*].to;

    int b=G[num*+].to;

    if(father[a]==b)

    {

        key=key-(getSum(number[a])-getSum(number[a]-));

        insert(number[a],key);

    }else

    {

        key=key-(getSum(number[b])-getSum(number[b]-));

        insert(number[b],key);

    }

}

int query(int from,int to)

{

    int ans=;

    int t1=top[from];

    int t2=top[to];

     // cout<<"check_top: "<<t1<<ends<<t2<<endl;

     // cout<<"check_point: "<<from<<ends<<to<<endl;

    while(t1!=t2)

    {

        if(deep[t1]<deep[t2])

        {

            swap(t1,t2);

            swap(from,to);

        }

        ans+=getSum(number[from])-getSum(number[t1]-);

        from=father[t1];

        t1=top[from];

    }

    int star=min(number[from],number[to]);

    int endd=max(number[from],number[to]);

     // cout<<ans<<"check_Number: "<<star<<ends<<endd<<endl;

     // cout<<"checkSum: "<<getSum(endd)<<ends<<getSum(star)<<endl;

    ans+=getSum(endd)-getSum(star);

    return ans;

}

void init()

{

    size=;summ=;

    memset(points,-,sizeof(points));

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

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        // cin>>a>>b>>c;

        add(a,b,c);

        add(b,a,c);

    }dfs_1(,,);

    dfs(,,);

    for(int i=;i<q;++i)

    {

        int a,b,c;

        // cin>>c;

        scanf("%d",&c);

        if(c)

        {

            // cin>>a>>b;

            scanf("%d%d",&a,&b);

            a--;

            update(a,b);

        }else{

            // cin>>a;

            scanf("%d",&a);

            cout<<query(s,a)<<"\n";

            s=a;

        }

    }

}

int main()

{

    // cin.sync_with_stdio(false);

    cin>>n>>q>>s;init();

    return ;

}