HDUOJ 4836 The Query on the Tree

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4836

题意:略。

思路:抛开操作三不管,那么我们用DFS序和树状数组维护一下区间信息就可以了,对于操作三,我们可以分情况讨论:1.如果root改变后是x的祖先的话,那么对以x为根节点的子树是没有影响的,直接输出就好;2.如果root改变后就是x,那么我们直接输出整个树的权值和就好了;3.如果root改变后在x的子树中,我们假设x经过它的某个子节点y到达root,那么很明显当前x的子树和,应该是整棵树的权值和减去原来y对应的子树的权值和,因为x-y这条边是root进行dfs到达x的最后一条边,换句话说这条边就把是不是x的子树的点分隔开了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
char op[10];
int T,n,q,dfs_clock,root,x,y;
int l[maxn],r[maxn],dep[maxn],parent[maxn][16],sum[maxn<<1],val[maxn];
vector<int>G[maxn];
void dfs(int u,int f){
    dep[u]=(u==1?1:dep[f]+1);
    l[u]=++dfs_clock;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        parent[v][0]=u;
        dfs(v,u);
    }
    r[u]=++dfs_clock;
}
void initLCA(){
    for (int k=0;k<15;k++){
        for (int v=1;v<=n;v++){
            if (parent[v][k]<0) continue;
            parent[v][k+1]=parent[parent[v][k]][k];
        }
    }
}
int lca(int u,int v){
    if (dep[u]>dep[v]) swap(u,v);
    for (int k=0;k<16;k++){
        if (((dep[v]-dep[u])>>k)&1) v=parent[v][k];
    }
    if (u==v) return u;
    for (int k=15;k>=0;k--){
        if (parent[u][k]!=parent[v][k]){
            u=parent[k][u];
            v=parent[k][v];
        }
    }
    return parent[u][0];
}
void init(){
    memset(parent,-1,sizeof(parent));
    memset(sum,0,sizeof(sum));
    for (int i=1;i<=n;i++) G[i].clear();
    dfs_clock=0;
}
int lowbit(int x){return x&(-x);}
void add(int x,int k){
    while (x<=dfs_clock){
        sum[x]+=k;
        x+=lowbit(x);
    }
}
int getSum(int x){
    int ret=0;
    while (x){
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
int query(int u){
    if (u==root) return getSum(dfs_clock);
    int v=lca(root,u);
    if (v!=u) return getSum(r[u])-getSum(l[u]-1);
    for (int i=0;i<(int)G[u].size();i++){
        int vv=G[u][i];
        if (dep[vv]<dep[u]) continue;
        v=lca(root,vv);
        if (v==vv) return getSum(dfs_clock)-(getSum(r[vv])-getSum(l[vv]-1));
    }
    return 0;
}
int main(){
    int cas=1;
    for (read(T);T;T--){
        read(n);
        init();
        for (int i=1;i<n;i++){
            int u,v;read(u),read(v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1,-1);
        for (int i=1;i<=n;i++){
            read(val[i]);
            add(l[i],val[i]);
        }
        initLCA();
        root=1;
        printf("Case #%d:\n",cas++);
        for (read(q);q;q--){
            scanf("%s",op);
            if (op[0]=='Q'){
                read(x);
                printf("%d\n",query(x));
            }
            else if (op[0]=='C'){
                read(x),read(y);
                add(l[x],y-val[x]);
                val[x]=y;
            }
            else{
                read(x);
                root=x;
            }
        }
    }
    return 0;
}

发表评论

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