「Luogu P3178」[HAOI2015]树上操作

发表于 |
字数统计: 1.2k | 阅读时长 ≈ 6

给定一棵树和多个操作，对于每一个操作3，回答该询问的答案。

链接

Luogu P3178
BZOJ 4034

题解

树链剖分板子题。对于每一个1操作，直接将起点和终点设为这个点，执行路径修改。对于操作2和操作3，直接使用树剖板子。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct edge{
    ll to,prev;
};
struct SegmentTree{
    ll l,r,sum,tag;
};
edge ed[200051];
SegmentTree tree[200051<<2];
ll last[200051],val[200051],depth[200051],fa[200051],size[200051],heavy[200051];
ll id[200051],pre[200051],top[200051];
ll tot,nc,cnt,ccnt,op,x,y,from,to;
inline ll read()//快读
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to)//邻接表基本操作
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    last[from]=tot;
}
//线段树基本操作
inline void update(ll node)//更新节点值，用位运算优化
{
    tree[node].sum=tree[node<<1].sum+tree[(node<<1)|1].sum;
}
inline void create(ll l,ll r,ll node)//建树
{
    tree[node].l=l,tree[node].r=r;
    if(l==r)
    {
        tree[node].sum=val[l];
        return;
    }
    ll mid=(l+r)>>1;
    create(l,mid,node<<1);//建左子树
    create(mid+1,r,(node<<1)|1);//建右子树
    update(node);//更新当前节点
}
inline void spread(ll node)//下传懒标记
{
    if(tree[node].tag)
    {
        //更新节点信息
        tree[node<<1].sum+=tree[node].tag*(tree[node<<1].r-tree[node<<1].l+1);
        tree[(node<<1)|1].sum+=tree[node].tag*(tree[(node<<1)|1].r-tree[(node<<1)|1].l+1);
        //下传懒标记
        tree[node<<1].tag+=tree[node].tag;
        tree[(node<<1)|1].tag+=tree[node].tag;
        //清除当前节点懒标记
        tree[node].tag=0;
    }
}
inline void add(ll l,ll r,ll val,ll node)
{
    if(l<=tree[node].l&&r>=tree[node].r)
    {
        tree[node].sum+=val*(tree[node].r-tree[node].l+1);
        //做标记
        tree[node].tag+=val;
        return;
    }
    spread(node);//标记下传
    ll mid=(tree[node].l+tree[node].r)>>1;
    if(l<=mid)
    {
        add(l,r,val,node<<1);
    }
    if(r>mid)
    {
        add(l,r,val,(node<<1)|1);
    }
    update(node);
}
inline ll query(ll l,ll r,ll node) 
{
    if(l<=tree[node].l&&r>=tree[node].r)
    {
        return tree[node].sum;
    }
    spread(node);//标记下传
    ll mid=(tree[node].l+tree[node].r)>>1,val=0;
    if(l<=mid)
    {
        val+=query(l,r,node<<1);
    }
    if(r>mid)
    {
        val+=query(l,r,(node<<1)|1);
    }
    return val;
}
inline void dfs(ll node,ll f,ll dep)
{
    depth[node]=dep,fa[node]=f,size[node]=1;//更新节点深度，父节点，节点为根的子树大小
    ll maxn=-1;//重儿子
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to!=f)//遍历子节点
        {
            dfs(ed[i].to,node,dep+1);
            size[node]+=size[ed[i].to];//更新子树大小
            if(size[ed[i].to]>maxn)
            {
                heavy[node]=ed[i].to,maxn=size[ed[i].to];//标记重儿子
            }
        }
    }
}
inline void ddfs(ll node,ll link)
{
    id[node]=++ccnt,val[ccnt]=pre[node],top[node]=link;//标记节点新编号，赋初始值，更新节点所在重链的顶部
    if(!heavy[node])//连重儿子都没有，肯定没有轻儿子，回溯
    {
        return;
    }
    ddfs(heavy[node],link);//先遍历重儿子
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to!=fa[node]&&ed[i].to!=heavy[node])
        {
            ddfs(ed[i].to,ed[i].to);//遍历轻儿子，该节点所在重链顶部节点为自己
        }
    }
}
//无脑操作
inline ll queryPath(ll x,ll y)//查询路径点权和
{
    ll ans=0;
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
        {
            swap(x,y);
        }
        ans+=query(id[top[x]],id[x],1);//加上整个链的点权和
        x=fa[top[x]];//爬到链顶
    }
    if(depth[x]>depth[y])
    {
        swap(x,y);
    }
    ans+=query(id[x],id[y],1);
    return ans;
}
inline ll querySubtree(ll root)
{
    return query(id[root],id[root]+size[root]-1,1);
}
inline void changePath(ll x,ll y,ll val)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])
        {
            swap(x,y);
        }
        add(id[top[x]],id[x],val,1);
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])
    {
        swap(x,y);
    }
    add(id[x],id[y],val,1);
}
inline void changeSubtree(ll root,ll val)
{
    add(id[root],id[root]+size[root]-1,val,1);
}
int main()
{
    nc=read(),cnt=read();
    for(register int i=1;i<=nc;i++)
    {
        pre[i]=read();
    }
    for(register int i=0;i<nc-1;i++)
    {
        from=read(),to=read();
        addEdge(from,to),addEdge(to,from);
    }
    dfs(1,0,1),ddfs(1,1),create(1,nc,1);
    for(register int i=0;i<cnt;i++)
    {
        op=read();
        switch(op)
        {
            case 1:{
                x=read(),y=read();
                changePath(x,x,y);
                break;
            }
            case 2:{
                x=read(),y=read();
                changeSubtree(x,y);
                break;
            }
            case 3:{
                x=read();
                cout<<queryPath(x,1)<<endl;
                break;
            }
        }
    }
}