hdu 3289 Magic tree （最大生成树 + dfs +树状数组）

题意：对一棵树上的点进行实时的增减权值和询问子树的权值和

首先：单点修改以及子树查询。对整棵树dfs一遍，记录下欧拉序列。这样有一个好处，就是每一棵子树在这个序列中都是连续的，同时记录下每一棵子树的起始序列号，这样，对子树的查询就变成了一个连续区间的查询了，运用树状数组就可以解决了。

那最大生成树呢？“Sailormoon girls want to cut extra branches by using minimum cost, after that..."额，这里要将多余的边减掉，用最小cost，也就是减掉之后，变成了一棵最大生成树。郁闷呀，一开始以为题目所给的cost是没用…………

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 100010;
int spos[MAXN],epos[MAXN],sum[MAXN],w[MAXN];
int n,f[MAXN],index;
bool vis[MAXN];
struct edge
{
    int u,v,w;
    edge(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
    bool friend operator<(const edge a,const edge b)
    {
        return a.w<b.w;
    }
};
priority_queue<edge> Q;
vector<int> g[MAXN];
void init()
{
    for(int i=0;i<=n;i++)
    {
        f[i]=i;
        w[i]=sum[i]=0;
        g[i].clear();
    }
}
int find(int x)
{
    if(x==f[x])
        return f[x];
    f[x]=find(f[x]);
    return f[x];
}
void Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b) return ;
    f[a]=b;
    g[x].push_back(y);//重新构建树
    g[y].push_back(x);
}
void Kruskal()//将所有边压入优先队列，再取出所有边合并，求最大生成树
{
    while(!Q.empty())
    {
        Union(Q.top().u,Q.top().v);
        Q.pop();
    }
}
int lowbit(int x)//这里往下三个函数就是树状数组的模板函数了，就不多说了
{
    return x&(-x);
}
void modify(int x,int add)
{
    while(x<=n)
    {
        sum[x]+=add;
        x+=lowbit(x);
    }
}
int get_sum(int x)
{
    int ret=0;
    while(x!=0)
    {
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
void dfs(int u)
{
    spos[u]=index;//记录子树的起始位置
    vis[u]=true;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!vis[v])
        {
            index++;
            dfs(v);
        }
    }
    epos[u]=index;//记录子树的终点位置
}
int main()
{
    int m,k,a,b,c;
    char str[5];
    while(scanf("%d %d",&n,&m)==2)
    {
        init();
        while(m--)
        {
            scanf("%d %d %d",&a,&b,&c);
            Q.push(edge(a,b,c));
        }
        Kruskal();
        index=1;
        memset(vis,false,sizeof(vis));
        dfs(1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='G')
            {
                scanf("%d %d",&a,&c);
                modify(spos[a],c);
                w[a]+=c;
            }
            else if(str[0]=='C')
            {
                scanf("%d",&a);
                modify(spos[a],-w[a]);
                w[a]=0;
            }
            else {
                scanf("%d",&a);
                int ans=get_sum(epos[a])-get_sum(spos[a]-1);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}