HDU 4836 The Query on the Tree

正文索引 [隐藏]

题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4836

题解

我们不动树的形态，而直接判断根和查询点的位置关系。
首先如果，根和查询点重合，直接求整个树的和。
如果根的深度<查询点的深度或者，那么直接查询这个点所在子树和即可。
如果根的深度>查询点且根向上跳深度差那么多步刚好调到查询点，那么只需要求整颗树的和-根所在的查询点孩子的那片子树的和即可。
如果都不满足，那么直接查询这个点所在子树和即可。
只需要DFS序+倍增父亲节点即可。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
using namespace std;
const int Maxd=20;
const int Maxn=10000;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
Edge e[Maxn*2+5];
int nume;
int head[Maxn+5];
int n;
int sum[Maxn+5];
int fa[Maxn+5][25];
int dep[Maxn+5];
int inDfn[Maxn+5];
int outDfn[Maxn+5];
int dfn;
int Root;
int num[Maxn+5];
inline void init(){
    dfn=0;
    memset(head,0,sizeof(head));
    memset(sum,0,sizeof(sum));
    nume=0;
    Root=1;
}
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}
void dfs(int x){
    for (int i=1;i<=Maxd;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    inDfn[x]=++dfn;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (fa[x][0]==v) continue;
        fa[v][0]=x;
        dep[v]=dep[x]+1;
        dfs(v);
    }
    outDfn[x]=dfn;
}
inline int lowbit(int x){
    return x&-x;
}
inline void add(int x,int val){
    for (int i=x;i<=Maxn;i+=lowbit(i))
        sum[i]+=val;
}
inline int get(int x){
    int ret=0;
    for (int i=x;i;i-=lowbit(i))
        ret+=sum[i];
    return ret;
}
inline int swim(int x,int dep){
    for (int i=0;i<=Maxd;i++)
        if ((dep&(1<<i))>0) x=fa[x][i];
    return x;
}
inline void solve(int T){
    init();
    printf("Case #%d:\n",T);
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    fa[1][0]=0;
    dep[1]=1;
    dfs(1);
    for (int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        add(inDfn[i],num[i]);
    }
    int q;
    char ord[20];
    scanf("%d",&q);
    for (int i=1;i<=q;i++){
        scanf("%s",ord);
        if (ord[0]=='C'){
            int x,y;
            scanf("%d%d",&x,&y);
            add(inDfn[x],-num[x]);
            add(inDfn[x],y);
            num[x]=y;
        }else if (ord[0]=='Q'){
            int x;
            scanf("%d",&x);
            if (dep[x]>dep[Root])
                printf("%d\n",get(outDfn[x])-get(inDfn[x]-1));
            else if (x==Root)
                printf("%d\n",get(outDfn[1]));
            else if(swim(Root,dep[Root]-dep[x])==x)
                printf("%d\n",get(outDfn[1])-(get(outDfn[swim(Root,dep[Root]-dep[x]-1)])-get(inDfn[swim(Root,dep[Root]-dep[x]-1)]-1)));
            else
                printf("%d\n",get(outDfn[x])-get(inDfn[x]-1));
        }else{
            scanf("%d",&Root);
        }
    }
}
int main(){
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve(i);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

//while(true) RP++;

#include<cstdio>

#include<cstring>

using namespace std;

const int Maxd=20;

const int Maxn=10000;

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

Edge e[Maxn*2+5];

int nume;

int head[Maxn+5];

int n;

int sum[Maxn+5];

int fa[Maxn+5][25];

int dep[Maxn+5];

int inDfn[Maxn+5];

int outDfn[Maxn+5];

int dfn;

int Root;

int num[Maxn+5];

inline void init(){

dfn=0;

memset(head,0,sizeof(head));

memset(sum,0,sizeof(sum));

nume=0;

Root=1;

}

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

e[++nume]=Edge(u,head[v]);

head[v]=nume;

}

void dfs(int x){

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

fa[x][i]=fa[fa[x][i-1]][i-1];

inDfn[x]=++dfn;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (fa[x][0]==v) continue;

fa[v][0]=x;

dep[v]=dep[x]+1;

dfs(v);

}

outDfn[x]=dfn;

}

inline int lowbit(int x){

return x&-x;

}

inline void add(int x,int val){

for (int i=x;i<=Maxn;i+=lowbit(i))

sum[i]+=val;

}

inline int get(int x){

int ret=0;

for (int i=x;i;i-=lowbit(i))

ret+=sum[i];

return ret;

}

inline int swim(int x,int dep){

for (int i=0;i<=Maxd;i++)

if ((dep&(1<<i))>0) x=fa[x][i];

return x;

}

inline void solve(int T){

init();

printf("Case #%d:\n",T);

scanf("%d",&n);

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

int x,y;

scanf("%d%d",&x,&y);

addEdge(x,y);

}

fa[1][0]=0;

dep[1]=1;

dfs(1);

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

scanf("%d",&num[i]);

add(inDfn[i],num[i]);

}

int q;

char ord[20];

scanf("%d",&q);

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

scanf("%s",ord);

if (ord[0]=='C'){

int x,y;

scanf("%d%d",&x,&y);

add(inDfn[x],-num[x]);

add(inDfn[x],y);

num[x]=y;

}else if (ord[0]=='Q'){

int x;

scanf("%d",&x);

if (dep[x]>dep[Root])

printf("%d\n",get(outDfn[x])-get(inDfn[x]-1));

else if (x==Root)

printf("%d\n",get(outDfn[1]));

else if(swim(Root,dep[Root]-dep[x])==x)

printf("%d\n",get(outDfn[1])-(get(outDfn[swim(Root,dep[Root]-dep[x]-1)])-get(inDfn[swim(Root,dep[Root]-dep[x]-1)]-1)));

else

printf("%d\n",get(outDfn[x])-get(inDfn[x]-1));

}else{

scanf("%d",&Root);

}

int main(){

int T=0;

while(scanf("%d",&T)!=EOF)

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

solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑

HDU 4836 The Query on the Tree

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

HDU 4836 The Query on the Tree

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗