【2018.8.8】JZ集训倒数第13天

又是风(yin)和(qing)日(bu)丽(ding)的美好的一天JZ生活呢  ^.^

  • 题目:

  • To your surprise, Jamie is the final boss! Ehehehe.

    Jamie has given you a tree with nn vertices, numbered from 11 to nn . Initially, the root of the tree is the vertex with number 11 . Also, each vertex has a value on it.

    Jamie also gives you three types of queries on the tree:

    1\ v1 v — Change the tree's root to vertex with number vv .

    2\ u\ v\ x2 u v x — For each vertex in the subtree of smallest size that contains uu and vv , add xx to its value.

    3\ v3 v — Find sum of values of vertices in the subtree of vertex with number vv .

    A subtree of vertex vv is a set of vertices such that vv lies on shortest path from this vertex to root of the tree. Pay attention that subtree of a vertex can change after changing the tree's root.

    Show your strength in programming to Jamie by performing the queries accurately!

  • 题目大意: 

  • 给出一棵树,支持三种操作:
    • 1.改变树的根节点
    • 2.求两点的lca,并对lca的子树的所有节点权值加上一个数
    • 3.询问一个节点子树的所有节点权值和

QWQ

  • 考试思路:

    • lca打了倍增,接下来思考如何解决没有换根操作的子任务,比较自然地想到DFS序+线段树/树状数组可以解决,但没有充分考虑时间复杂度,导致该部分TLE。。。

  • 正解思路:

    •         如果没有换根操作,那么这就是一道裸题:只需要用线段树/树状数组维
      护DFS上的权值和即可。需要支持换根操作时,我们也并不需要真的换个根,而
      只需要用一个变量记录当前的根root。
              经过一些简单的讨论可以知道,u和v在以root为根时的lca为:lca(u, v),
      lca(u, root), lca(v, root)中原来深度最大的一个,其中lca(a, b)代表a, b 在以1为
      根时的lca。根据root是否在原来u的子树内,我们可以轻易提取出以root为根
      时u的子树对应的区间。
              于是这还是一道裸题,O(q log n)
    •         其实思考时已经比较接近了正解思路,不过对于换根操作并没有想到巧妙地转换,通过分类讨论root与lca的关系,可以较方便地完成各项操作OwO
    •         因为JZOJ的时限只给了1S,所以愉快地被卡常了Orz,听神犇们说可以使用树链剖分来优化,还未实现QWQ

  • 代码实现

    
    
    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    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
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    using namespace std;

    const int N=3*1e5+10;

    int num,n,q,e[N],tot,Next[N],head[N],fa[N][21],vis[N];
    long long w[N],ans,val[N];
    int dep[N],rt,don;
    int tt,L[N],R[N];

    struct node
    {
        long long lm,rm,v,tag;
    }tree[N*4];


    int read(void)
    {
        char ch;
        int re=0,va=1;
        while (!(isdigit(ch=getchar()) || ch=='-'));
        if (ch=='-')    va=-1;
        else    re=ch-'0';
        while (isdigit(ch=getchar()))
            (re*=10)+=ch-'0';
        return re*va;
    }

    void adde(int x,int y)
    {
        e[++tot]=y;
        Next[tot]=head[x];
        head[x]=tot;
    }

    void jump(int &a,int c)
    {
        for (int i=0;i<=20;i++)
        {
            if (c&1)    a=fa[a][i];
            c>>=1;
        }
    }

    int Find(int a,int b)
    {
        if (dep[a]<dep[b])  swap(a,b);
        jump(a,dep[a]-dep[b]);
        if (a==b)   return a;
        for (int i=20;i>=0;i--)
        {
            if (fa[a][i]!=fa[b][i])
            {
                a=fa[a][i];
                b=fa[b][i];
            }
        }
        return fa[a][0];
    }

    void downtag(int root)
    {
        if (tree[root].tag)
        {
            tree[2*root].v+=(long long)(tree[2*root].rm-tree[2*root].lm)*tree[root].tag;
            tree[2*root].tag+=tree[root].tag;
            tree[2*root+1].v+=(long long)(tree[2*root+1].rm-tree[2*root+1].lm)*tree[root].tag;
            tree[2*root+1].tag+=tree[root].tag;
            tree[root].tag=0;
        }
    }
     
    void amend(int root,int ls,int rs,int c)
    {
        if (ls<=tree[root].lm && tree[root].rm<=rs)
        {
            tree[root].v+=(long long)(tree[root].rm-tree[root].lm)*c;
            tree[root].tag+=c;
            return;
        }
        downtag(root);
       
        int mid=(tree[root].lm+tree[root].rm)/2;
       
        if (ls<mid)
        {
            amend(root*2,ls,rs,c);
        }
        if (mid<rs)
        {
            amend(root*2+1,ls,rs,c);
        }
        tree[root].v=tree[root*2].v+tree[root*2+1].v;
    }
     
    long long query(int root,int ls,int rs)
    {
        if (ls<=tree[root].lm && tree[root].rm<=rs)
        {
            return tree[root].v;
        }
        downtag(root);
       
        int mid=(tree[root].lm+tree[root].rm)/2;
        long long ans=0;
        if (ls<mid)
        {
            ans+=query(root*2,ls,rs);
        }
        if (mid<rs)
        {
            ans+=query(root*2+1,ls,rs);
        }
     
        return ans;
    }
     
    void build(int root,int ls,int rs)
    {
        tree[root].lm=ls;
        tree[root].rm=rs;
        tree[root].v=0;
        tree[root].tag=0;
       
        if (ls<rs-1)
        {
            int mid=(ls+rs)/2;
            build(root*2,ls,mid);
            build(root*2+1,mid,rs);
            tree[root].v=tree[2*root].v+tree[2*root+1].v;
        }
        else
        {
            don++;
            tree[root].v=val[don];
        }
        return;
    }

    void dfs(int now,int f)
    {
        tt++,val[tt]=w[now];
        L[now]=R[now]=tt;
        dep[now]=dep[f]+1;
        fa[now][0]=f;
        for (int i=1;i<=20;i++)
            fa[now][i]=fa[fa[now][i-1]][i-1];
        int to;
        for (int nex=head[now];nex;nex=Next[nex])
        {
            to=e[nex];
            if (to!=f)
            {
                dfs(to,now);
                L[now]=min(L[now],L[to]);
                R[now]=max(R[now],R[to]);
            }
        }
    }

    bool check_son(int u,int v)
    {
        if (u==Find(u,v))   return true;
        return false;
    }

    void change_root(int r)
    {
        rt=r;
    }

    void change(int u,int v,int x)
    {
        int now=Find(u,v);
        if (!check_son(now,rt))     //若现根不在lca的子树里(原树上)
        {
            amend(1,L[now],R[now]+1,x);//则换根对于本次操作无影响,直接修改
            return;
        }
        amend(1,1,n+1,x);   //先每个点都+x
        int a=Find(rt,u),b=Find(rt,v);
        if (dep[a]>dep[b])  u=a;
        else    u=b;    //分别求出 root&u  root&v 的lca,深度较大的为换根后的lca(显然?)
        v=rt;
        if (u==v) return;   //若lca即为现根,无需减去值
        //因为现根在lca(最原始的u&v)的子树,故v的深度一定大于u的深度
        jump(v,dep[v]-dep[u]-1);
        amend(1,L[v],R[v]+1,-x);
    //  amend(1,L[u],R[u]+1,-x);    //不能直接用u的原因:u是lca,而u的L~R包含了其部分子树(在现根意义下)
                                    //故jump的时候-1;
    }

    long long ask(int now)
    {
        if (!check_son(now,rt))
        {
            return query(1,L[now],R[now]+1);
        }//若现根不在v的子树里(原树上),则换根对于本次操作无影响,直接查询
        long long ans=0;
        ans=query(1,1,1+n);
        int u=now,v=rt;
        if (u==v)   return ans; //特判now==root
        jump(v,dep[v]-dep[u]-1);    //同修改,注意要-1!
        ans-=query(1,L[v],R[v]+1);
        return ans;
    }


    int main(void)
    {
        freopen("tree.in","r",stdin);
        freopen("tree.out","w",stdout);

        scanf("%d%d",&n,&q);
        for (int i=1;i<=n;i++)  w[i]=read();
        int x,y,p;
        for (int i=1;i<=n-1;i++)
        {
            x=read(),y=read();
            adde(x,y);
            adde(y,x);
        }
        rt=1;
        dfs(1,0);
        build(1,1,1+n);
        int a,b,c;
        while (q--)
        {
            p=read();
            if (p==1)
            {
                a=read();
                change_root(a);
            }
            else
            if (p==2)
            {
                a=read(),b=read(),c=read();
                change(a,b,c);
            }      
            else
            {
                a=read();
                printf("%lld\n",ask(a));
            }
        }
       
        fclose(stdin);
        fclose(stdout);
       
        return 0;
    }
  • PS:有些结论比较明显能通过画图分类讨论得出不给出具体证明过程QwQ其实是不会证

 

十日画一水,五日画一石。

Y.W.

发表评论

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