[HDU 4836] | Eurce's Blog

2014年百度之星复赛的第二题，看了官方题解才会做。

个人觉得这题有意思的地方有：
（1）通过记录DFS顺序+树状数组的方式，动态更新每一棵子树的权值和；
（2）树根改变的时候，根据父子关系巧妙地不修改数据求出当前子树权值和。

#include<cstdio>
#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;
int tr[20001],yt,rt;
char s[10];

struct E
{
    int v,p;
}e[20000];

void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

void ins(int i,int d)
{
    while(i<di)
    {
        tr[i]+=d;
        i+=i&-i;
    }
}

int qry(int i)
{
    int d=0;
    while(i)
    {
        d+=tr[i];
        i-=i&-i;
    }
    return d;
}

void dfs(int i,int h)
{
    int j,k,l;
    f[i]=h;
    dl[i]=di++;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(j==h)
            continue;
        dfs(j,i);
    }
    dr[i]=di++;
}

void init()
{
    int i,j,k,l;
    el=0;
    di=1;
    yt=0;
    rt=0;
    memset(hd,-1,sizeof hd);
    memset(tr,0,sizeof tr);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        adde(j-1,k-1);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",y+i);
        yt+=y[i];
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        ins(dl[i],y[i]);
}

void solve()
{
    int i,j,k,l;
    printf("Case #%d:\n",++t);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%d",&i);
            i--;
            if(i==rt)
            {
                printf("%d\n",yt);
            }
            else
            {
                if(dl[rt]>dl[i]&&dr[rt]<dr[i])
                {
                    for(l=rt;f[l]!=i;l=f[l]);
                    printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));
                }
                else
                {
                    printf("%d\n",qry(dr[i])-qry(dl[i]-1));
                }
            }
        }
        else if(s[0]=='C')
        {
            scanf("%d%d",&i,&j);
            i--;
            ins(dl[i],j-y[i]);
            yt+=j-y[i];
            y[i]=j;
        }
        else
        {
            scanf("%d",&rt);
            rt--;
        }
    }
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<cstdio>

#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;

int tr[20001],yt,rt;

char s[10];

struct E

{

int v,p;

}e[20000];

void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

void ins(int i,int d)

{

while(i<di)

{

tr[i]+=d;

i+=i&-i;

}

int qry(int i)

{

int d=0;

while(i)

{

d+=tr[i];

i-=i&-i;

}

return d;

}

void dfs(int i,int h)

{

int j,k,l;

f[i]=h;

dl[i]=di++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(j==h)

continue;

dfs(j,i);

}

dr[i]=di++;

}

void init()

{

int i,j,k,l;

el=0;

di=1;

yt=0;

rt=0;

memset(hd,-1,sizeof hd);

memset(tr,0,sizeof tr);

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

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

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

{

scanf("%d",y+i);

yt+=y[i];

}

dfs(0,-1);

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

ins(dl[i],y[i]);

}

void solve()

{

int i,j,k,l;

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

scanf("%d",&m);

while(m--)

{

scanf("%s",s);

if(s[0]=='Q')

{

scanf("%d",&i);

i--;

if(i==rt)

{

printf("%d\n",yt);

}

else

{

if(dl[rt]>dl[i]&&dr[rt]<dr[i])

{

for(l=rt;f[l]!=i;l=f[l]);

printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));

}

else

{

printf("%d\n",qry(dr[i])-qry(dl[i]-1));

}

else if(s[0]=='C')

{

scanf("%d%d",&i,&j);

i--;

ins(dl[i],j-y[i]);

yt+=j-y[i];

y[i]=j;

}

else

{

scanf("%d",&rt);

rt--;

}

int main()

{

scanf("%*d");

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}