(luogu3178) 树上操作 (HAOI2015)

发表于 分类于 ， ，

树链剖分第一题，难度：简单

树链剖分笔记索引

思路:

树链剖分 + 线段树区间和

详细操作还是写在代码注释里好了

代码:

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
#include <cstdio>
#include <iostream>
#include <cctype>
using namespace std;
const int Mn(100005);
long long qrd()    //快读
{
    long long x(0),f(1); char c(getchar());
    while(!isdigit(c))
    {
        if(c=='-')  f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n;
struct edge    //边表, 存树
{
    int e,nt;
}ed[Mn*2];
int vs[Mn],ec(0);
long long d[Mn];
void adde(int s,int e)    //边表加边
{
    ed[++ec].e=e; ed[ec].nt=vs[s];
    vs[s]=ec;
}
int dp[Mn],sz[Mn],pa[Mn],hs[Mn];    //深度, 子树大小, 父结点, 重儿子
void dfs1(int x)    //寻找重儿子
{
    sz[x] = 1;
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(!dp[ntn])
        {
            dp[ntn] = dp[x]+1;
            pa[ntn] = x;
            dfs1(ntn);
            sz[x] += sz[ntn];
            if(sz[hs[x]]<sz[ntn]) hs[x]=ntn;
        }
    }
}
struct tn    //线段树的结点域
{
    int l,r;    //区间左右端点
    long long v,lt;    //区间和, 懒标记
}t[Mn<<2];
int cd[Mn],tp[Mn],dc(0);    //结点访问时间, 链顶, 时间戳
long long a[Mn];    //剖分后的序列
void dfs2(int x)    //重儿子拉成链
{
    a[++dc] = d[x];
    cd[x] = dc;
    if(hs[x])
       tp[hs[x]]=tp[x], dfs2(hs[x]);
    for(int e(vs[x]);e;e=ed[e].nt)
    {
        int& ntn(ed[e].e);
        if(dp[ntn]>dp[x] && ntn!=hs[x])
            tp[ntn] = ntn, dfs2(ntn);
    }
}
void bud(int l,int r,int rt)    //构建线段树
{
    if(l==r)
    {
        t[rt].l=t[rt].r=l;
        t[rt].v=a[l];
        return;
    }
    int mid((l+r)>>1);
    bud(l,mid,rt<<1);
    bud(mid+1,r,rt<<1|1);
    t[rt].l = l, t[rt].r = r;
    t[rt].v = t[rt<<1].v+t[rt<<1|1].v;
}
void pd(int rt)    //下放标记
{
    if(t[rt].lt)
    {
        t[rt<<1].lt += t[rt].lt;
        t[rt<<1|1].lt += t[rt].lt;
        t[rt<<1].v += (t[rt<<1].r-t[rt<<1].l+1)*t[rt].lt;
        t[rt<<1|1].v += (t[rt<<1|1].r-t[rt<<1|1].l+1)*t[rt].lt;
        t[rt].lt = 0;
    }
}
void mdf(int rt,int ml,int mr,long long a)    //线段树修改
{
    int& xl(t[rt].l),&xr(t[rt].r);
    if(xl>=ml && xr<=mr)
    {
        t[rt].v += (xr-xl+1)*a;
        t[rt].lt += a;
        return;
    }
    pd(rt);
    int mid((xl+xr)>>1);
    if(ml<=mid) mdf(rt<<1,ml,mr,a);
    if(mr>mid)  mdf(rt<<1|1,ml,mr,a);
    t[rt].v = t[rt<<1].v+t[rt<<1|1].v;
}
long long qry(int rt,int ql,int qr)    //线段树查询
{
    int& xl(t[rt].l),&xr(t[rt].r);
    if(xl>=ql && xr<=qr)
        return t[rt].v;
    pd(rt);
    int mid((xl+xr)>>1);
    long long ret(0);
    if(ql<=mid) ret += qry(rt<<1,ql,qr);
    if(qr>mid)  ret += qry(rt<<1|1,ql,qr);
    return ret;
}
int main()
{
    n = qrd();
    int m(qrd());
    for(int i(1);i<=n;++i)
        d[i] = qrd();
    for(int i(1);i<n;++i)
    {
        int x(qrd()),y(qrd());
        adde(x,y), adde(y,x);
    }
    /*----初始化----*/
    dp[1]=1,pa[1]=0,tp[1]=1; dfs1(1);
    dfs2(1);
    bud(1,n,1);
    /*--------*/
    while(m--)
    {
        int o(qrd()),x;
        long long a;
        switch(o)
        {
            case 1:
                x=qrd(), a=qrd();
                mdf(1,cd[x],cd[x],a);    //更改单结点
                break;
            case 2:
                x=qrd(), a=qrd();
                mdf(1,cd[x],cd[x]+sz[x]-1,a);    //更改子树
                break;
            case 3:
                x=qrd();
                long long ret(0);
                while(x)    //重复查询从x结点到根节点的所有重链的和
                {
                    ret += qry(1,cd[tp[x]],cd[x]);
                    x = pa[tp[x]];
                }
                printf("%lld\n",ret);
                break;
        }
    }
    return 0;
}