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

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

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

#include
      
        #include
       
         #include
        
          #include
         
           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
          
            Q; vector
           
             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