OI - 神J上树(牛客)

这个难度梯度……第一题普及组T2、第二题普及组T3……第三题……提高组Day1T3?


Part1. 题面

神树大人和神 J 来到了神仙树公园。遗憾的是,神仙树公园里没有任何神仙树,只有一棵 $n$ 个点的普普通通的有根树(以1号点为根)。这棵树每条边有边权。

神 J 打算在这棵树上来回横跳,但神 J 每次只能从一个节点 $u$ 跳到它的子孙 $v$,代价为$u\times dist(u,v)$。$v$ 是 $u$ 的子孙当且仅当 $u$ 在 $v$ 到根节点的路径上。

神 J 提出了 $m$ 个询问,每次询问两个点 $s,t$,由于你是神树大人和神J的司机(??),所以神 J 想让你尽快告诉他是否能从 $s$ 到 $t$,如果能到则最小代价为多少。

数据规模:$n,m\leq300000$,$1\leq w_i\leq10^7$


Part2. 解析

> Hint.
你需要读懂题面才能理解下面的“显然”(然后你就会发觉的确很显然)

显然只有 $t$ 是 $s$ 的子孙才能从 $s$ 跳到 $t$,而且跳的过程中,神 J 一定在 $u$ 到 $v$ 的路径上(即任何一次跳跃的落点都在 $u$ 到 $v$ 的路径上)。

于是判断能否从 $s$ 到 $t$,倍增或者树链剖分求 LCA 就好了(LCA(u,v)=u)。

又因为神 J 只能向子孙跳,所以落点的深度是递增的
于是就有了一个非常显然的贪心思路,先把 $s$ 到 $t$ 的链单独拿出来;每次跳跃的落点就是在当前点下方的第一个比当前点小的点,或者如果没有这种点,就直接跳到 $t$,结束跳跃。

这个思路显然是正确的

> Prove

如果从当前点 $u$ 跳到点 $v$,$u,v$ 之间有一个小于 $u$ 的点 $w$。那么对比 $u\to v$ 和 $u\to w\to v$:

  1. 两种方案中 $u\to w$ 的路径的代价都是 $u\times dist(u,w)$;
  2. $w\to v$ 的路径的代价:第一种方案 $u\times dist(w,v)$,第二种方案 $w\times dist(w,v)$,第二种更优。

其实比较显然吧。

其实就是要找到 $s\to v$ 这条链上从 $s$ 开始的一条节点编号单调下降的序列

但是不可能每次询问都 $O(n)$ 遍历一遍 $s$ 到 $t$ 的路径吧……看了一下数据规模,似乎 $O(n\log_2^2n)$ 刚好能过。于是考虑加速计算 $s$ 到 $t$ 这条链上的单调下降序列。

树上对于一条链的操作,有树链剖分、倍增,这里用到的是树链剖分

> Hint.

树链剖分会将一棵树剖分成 $O(n)$ 条链(比如菊花图),但是每条树上的链会被剖分成 $O(\log_2 n)$ 条。

(以下“树链”均表示树链剖分剖出的链)

先处理出每一条树链上的“从该链的顶端开始的下降序列”。然后就要考虑如何将两条相邻的树链的下降序列合并了,比如下面这样:

jpg1

首先要提取出绿色链的 $s\to1$ 的这一段的下降序列,记该下降序列的最后一个元素是 x,然后与橙色链中 $2\to2$ 这一段的下降序列比较,舍去橙色链的下降序列中比x大的元素(两个下降序列合并,甚至有可能橙色链的下降序列所有元素都大于x,就会全部舍去)。再把 x 记为两个序列合并后的最后一个元素,然后继续合并,直到到达 $t$。

然而我们发现,一条树链的长度是 $O(n)$ —— 如果刻意构造一条长度与 $n$ 同阶、完全下降的树链,那么那条树链的下降序列长度规模就是 $O(n)$。这样的话,合并相邻的两个下降序列不可能再枚举第二条链上的哪些元素要被舍去。

(要合理利用好时间复杂度,还有一个 $O(\log_2n)$)合并两个下降序列 $A,B$,其实就是要在 $B$ 中找第一个比 $A$ 的末尾元素 x 小的元素 y,把 $B$ 中 y 元素之前的元素都舍去,再把 $A,B$ 两个序列接起来。

也就是“在一个下降序列中找第一个小于 x 的元素” —— 二分查找 ! 这样的话就把复杂度降到 $O(\log_2n)$ 了。

解决了合并下降序列的问题,就剩下求答案了。仍然不能遍历序列求解……最好是能 $O(\log_2n)$,这时候“序列深度递增”的性质就有用了 —— 可以倍增 求解 —— 先处理出每一个点 $u$ 在它所在的树链中的第 $2^i$ 个比它小的点,以及从 $u$ 出发、经过一些点到达第 $2^i$ 个比它小的点的最小代价。

实现起来还挺麻烦。不过总而言之这是一道不错的“树”题,用到了各种 $O(\log_2 n)$ 的算法。

> Tab.

其实可以用倍增替代掉二分查找,因为倍增数组也是单调递减的。


Part3. 源代码

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
/*Lucky_Glass*/
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=300000;

struct NODE{
int to,len;NODE *nxt;
NODE(){}
NODE(int _t,int _l,NODE *_n):to(_t),len(_l),nxt(_n){}
};
struct TREE{
NODE pol[N*2+3],*head[N+3],*ncnt;
TREE(){ncnt=pol;}
void AddEdge(int u,int v,int len){
NODE *p=++ncnt,*q=++ncnt;
*p=NODE(v,len,head[u]);head[u]=p;
*q=NODE(u,len,head[v]);head[v]=q;
}
NODE* operator [](int id){return head[id];}
}Tr;

int n,m,ndfn,nheadid;
//深度(带边权);重链上倍增的答案
ll dep[N+3],bzans[N+3][23];
//重儿子;子树大小;DFN;重链链头的编号(从1开始重编);父亲;倍增关键点;深度(无边权)
int wson[N+3],siz[N+3],dfn[N+3],headid[N+3],head[N+3],fa[N+3],prv[N+3][23],perdep[N+3];
//树链下降序列
vector< int > vec[N+3];
vector< pair< int,int > > wit;
stack< int > nowprev;

void DFS(int u,int fa){
perdep[u]=perdep[fa]+1;
::fa[u]=fa;
siz[u]++;
for(NODE *it=Tr[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
dep[v]=dep[u]+it->len;
DFS(v,u);
siz[u]+=siz[v];
if(siz[wson[u]]<siz[v]) wson[u]=v;
}
}
void DFN(int u,int fa,int head){
::head[u]=head;
if(u==head) headid[u]=++nheadid;
int id=headid[head];
if(vec[id].empty() || vec[id].back()>u) vec[id].push_back(u);
dfn[u]=++ndfn;
if(wson[u]) DFN(wson[u],u,head);
for(NODE *it=Tr[u];it;it=it->nxt){
int v=it->to;
if(v==fa || v==wson[u]) continue;
DFN(v,u,v);
}
}
void GainPrev(int u){
if(wson[u]) GainPrev(wson[u]);
while(!nowprev.empty() && nowprev.top()>u) nowprev.pop();
if(nowprev.empty()) prv[u][0]=0;
else{
prv[u][0]=nowprev.top();
bzans[u][0]=(dep[prv[u][0]]-dep[u])*u;
}
nowprev.push(u);
for(int i=1;i<=22;i++){
prv[u][i]=prv[prv[u][i-1]][i-1];
bzans[u][i]=bzans[u][i-1]+bzans[prv[u][i-1]][i-1];
}
}
int LCA(int u,int v){
while(head[u]!=head[v]){
if(perdep[head[u]]>perdep[head[v]]) swap(u,v);
v=fa[head[v]];
}
if(perdep[u]>perdep[v]) swap(u,v);
return u;
}
int SearchEnd(int id,int pnt){
int l=0,r=vec[id].size();
while(l+1<r){
int m=(l+r)>>1;
if(vec[id][m]>=pnt) l=m;
else r=m;
}
return l;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v,l;scanf("%d%d%d",&u,&v,&l);
Tr.AddEdge(u,v,l);
}
DFS(1,0);
DFN(1,0,1);
for(int i=1;i<=n;i++)
if(head[i]==i){
while(!nowprev.empty()) nowprev.pop();
GainPrev(i);
}
while(m--){
int u,v;
scanf("%d%d",&u,&v);
if(LCA(u,v)!=u) printf("-1\n");
else{
ll resu=0;
if(head[u]==head[v]){
int copu=u;
for(int i=22;i>=0;i--)
if(prv[copu][i] && perdep[prv[copu][i]]<=perdep[v]){
resu+=bzans[copu][i];
copu=prv[copu][i];
}
resu+=copu*(dep[v]-dep[copu]);
printf("%lld\n",resu);
continue;
}
int nowp=head[v];
wit.clear();
while(head[fa[nowp]]!=head[u]){
wit.push_back(make_pair(head[fa[nowp]],fa[nowp]));
nowp=head[fa[nowp]];
}
int lim=fa[nowp];
int cop=u;
for(int i=22;i>=0;i--)
if(prv[cop][i] && perdep[prv[cop][i]]<=perdep[lim]){
resu+=bzans[cop][i];
cop=prv[cop][i];
}
for(int i=wit.size()-1;i>=0;i--){
int id=headid[wit[i].first];lim=wit[i].second;
int rem=vec[id][SearchEnd(id,cop)];
if(cop>rem){
resu+=cop*(dep[rem]-dep[cop]);
cop=rem;
for(int j=22;j>=0;j--)
if(prv[cop][j] && perdep[prv[cop][j]]<=perdep[lim]){
resu+=bzans[cop][j];
cop=prv[cop][j];
}
}
else{
if(prv[rem][0] && perdep[prv[rem][0]]<=perdep[lim]){
resu+=cop*(dep[prv[rem][0]]-dep[cop]);
cop=prv[rem][0];
for(int j=22;j>=0;j--)
if(prv[cop][j] && perdep[prv[cop][j]]<=perdep[lim]){
resu+=bzans[cop][j];
cop=prv[cop][j];
}
}
}
}
int id=headid[head[v]];
int rem=vec[id][SearchEnd(id,cop)];
if(cop>rem){
resu+=cop*(dep[rem]-dep[cop]);
cop=rem;
for(int i=22;i>=0;i--)
if(prv[cop][i] && perdep[prv[cop][i]]<=perdep[v]){
resu+=bzans[cop][i];
cop=prv[cop][i];
}
resu+=cop*(dep[v]-dep[cop]);
}
else{
if(!prv[rem][0])
resu+=cop*(dep[v]-dep[cop]);
else{
if(perdep[prv[rem][0]]>=perdep[v]) resu+=cop*(dep[v]-dep[cop]);
else{
resu+=cop*(dep[prv[rem][0]]-dep[cop]);
cop=prv[rem][0];
for(int i=22;i>=0;i--)
if(prv[cop][i] && perdep[prv[cop][i]]<=perdep[v]){
resu+=bzans[cop][i];
cop=prv[cop][i];
}
resu+=cop*(dep[v]-dep[cop]);
}
}
}
printf("%lld\n",resu);
}
}
return 0;
}

The End

Thanks for reading!

大样例卡了好久……

0%