题目大意
给一棵以$1$为根的树，有如下操作：
- 将一条边的边权加上$v$
- 割掉一些点，代价是点权和，询问一个点$x$的子树中叶子结点与$x$不连通的最小代价。
题目分析
这是一类神奇的题目，明天总结一下。
首先考虑静态的动规。
设状态$f(i)$表示让$i$与其叶子均不连通的最小点权和。
不难写出转移：
这样转移是$O(n)$的，现在我们尝试用树链剖分来维护它。
将重儿子单独拆分出来，得到新的转移式：
其中$son(i)$是重儿子。
如果我们将$f(i)$视为来自$f(son(i))$的变换，则其通过先加上$\sum_{j\in ch(i),j\neq son(i)}f(j)$，再与$a(i)$取$\min$来得到$f(i)$。
根据吉老师线段树的经验，不难发现这样将$v$变成$\min(v+a,b)$的变换$(a,b)$具有可合并性，但是合并有顺序限制，即不满足交换律。
然后直接套用树剖维护动规，这道题就可以做了。
代码
代码中的$f$即为$restf$。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
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005;
int n,q,step=0,root[maxn],pos[maxn],father[maxn],Depth[maxn],Size[maxn],Son[maxn],Top[maxn],Dfn[maxn];
LL f[maxn],val[maxn];
vector<int> edges[maxn],chain[maxn],tops;
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Son[Now]]<Size[Next])Son[Now]=Next;
}
if(!Son[Now])f[Now]=val[Now];
}
void Dfs2(int Now,int top) {
Top[Now]=top;
Dfn[Now]=++step;
chain[top].push_back(Now);
if(Now==top)tops.push_back(top);
if(Son[Now])Dfs2(Son[Now],top);
for(int Next:edges[Now]) {
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}
struct Tag {
LL a,b;
Tag(LL a=0,LL b=LLONG_MAX/4):a(a),b(b) {}
LL val() {return min(a,b);}
Tag operator + (const Tag & y) const {
return Tag(y.a+a,min(y.b+a,b)); //!!!
}
};
struct Segment_Tree {
struct Tree {
int left,right;
int lson,rson;
Tag tag;
Tree(int l=0,int r=0):left(l),right(r),lson(0),rson(0),tag(Tag()) {}
} tree[maxn<<2];
void build(int &index,int Left,int Right,int top) {
if(!index)index=++step;
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].tag=Tag(f[chain[top][Left-1]],val[chain[top][Left-1]]);
pos[chain[top][Left-1]]=Left;
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,top);
build(rs,mid+1,Right,top);
push_up(index);
}
void push_up(int index) {
tree[index].tag=tree[ls].tag+tree[rs].tag;
}
void modify(int index,int target,Tag v) {
if(target<tree[index].left||target>tree[index].right)return;
if(tree[index].left==tree[index].right) {
tree[index].tag=v;
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
Tag query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return Tag();
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].tag;
return query(ls,Left,Right)+query(rs,Left,Right);
}
} st;
bool cmp(int x,int y) {
return Depth[x]>Depth[y];
}
LL get_f(int x) {
return st.query(root[Top[x]],pos[x],chain[Top[x]].size()).val();
}
void Modify(int x,int v) {
val[x]+=v;
if(!Son[x])f[x]+=v;
for(int t; father[t=Top[x]]; x=father[t]) {
LL last=st.tree[root[t]].tag.val();
st.modify(root[t],pos[x],Tag(f[x],val[x]));
f[father[t]]+=-last+st.tree[root[t]].tag.val();
}
st.modify(root[Top[x]],pos[x],Tag(f[x],val[x]));
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)val[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1,0,1);
Dfs2(1,1);
sort(tops.begin(),tops.end(),cmp);
for(int x:tops) {
st.build(root[x],1,chain[x].size(),x);
if(father[x])f[father[x]]+=st.tree[root[x]].tag.val();
}
q=Get_Int();
while(q--) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int();
if(opt=='Q')printf("%lld\n",get_f(x));
else Modify(x,Get_Int());
}
return 0;
}
