「UOJ87」mx的仙人掌 - 虚仙人掌/虚圆方树 | Bill Yang's Blog

「UOJ87」mx的仙人掌 - 虚仙人掌/虚圆方树

题目大意

    现给定一棵仙人掌,每条边有一个正整数权值,每次给$k$个点(可以存在相同点),问从它们中选出两个点(可以相同),它们之间最短路的最大值是多少。
    边权不超过$2^{31}-1$,$tot$表示询问的总点数,$n,tot\le300000$


题目分析

对于总结点的限制,不难想到虚树。
虚仙人掌的建立可以使用圆方树来实现,可以证明虚圆方树和虚仙人掌是等价的。

我们先用一次Tarjan求点双建立出圆方树,然后套用以前的过程建立虚圆方树。
注意,建立虚圆方树可能会出现两个方点直接相连的情况,这样的情况在处理的时候不方便,不妨在每次加入方点的时候都添加一个圆点(环引出去的点)。
显然虚圆方树的点数还是$O(n)$的。

接下来就和裸的仙人掌求直径一样了,在圆方树上Dp,讨论一下当前点是方点还是圆点即可,如果是方点,用单调队列更新答案。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=300005*2;

struct Edge {
int from,to;
LL dist;
};

int n,m,q,root,step,BCC=0,New,Dfn[maxn],Lowlink[maxn],Belong[maxn],First[maxn],Last[maxn],Depth[maxn],p[maxn][25];
LL Length[maxn],f[maxn],Dist[maxn],Dist1[maxn],Dist2[maxn],ans=0;
vector<Edge>edges,edges2[maxn],tree[maxn];
vector<int>G[maxn],Circle[maxn],a;
stack<Edge>S;

void AddEdge(int x,int y,LL v) {
edges.push_back((Edge) {x,y,v});
G[x].push_back(edges.size()-1);
}

void AddEdge2(int x,int y,LL v) {
edges2[x].push_back((Edge) {x,y,v});
}

int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=20;
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(~p[a][i]&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}

int get_son(int Now,int target) {
for(int i=20; i>=0; i--)
if(~p[Now][i]&&Depth[p[Now][i]]>Depth[target])Now=p[Now][i];
return Now;
}

void AddEdge3(int x,int y) {
if(x>n&&x!=p[y][0]) { //方点连出
int son=get_son(y,x);
tree[x].push_back((Edge) {x,son,Dist[son]-Dist[x]});
x=son;
}
if(y>n&&x!=p[y][0]) {
int fa=p[y][0];
tree[x].push_back((Edge) {x,fa,Dist[fa]-Dist[x]});
x=fa;
}
if(x!=y)tree[x].push_back((Edge) {x,y,Dist[y]-Dist[x]});
}

bool cmp(int x,int y) {
return First[x]<First[y];
}

void Tarjan(int Now,int fa) {
step++;
Lowlink[Now]=Dfn[Now]=step;
for(int x:G[Now]) {
Edge& e=edges[x];
int Next=e.to;
if(!Dfn[Next]) {
S.push((Edge) {
Now,Next,e.dist
});
Tarjan(Next,x);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
if(Dfn[Now]<Lowlink[Next])AddEdge2(Now,Next,e.dist),S.pop();
else if(Dfn[Now]==Lowlink[Next]) { //构成点双连通分量
BCC++;
AddEdge2(Now,++New,0);
while(!S.empty()) {
int u=S.top().from,v=S.top().to,dist=S.top().dist;
S.pop();
Length[BCC]+=dist;
f[u]=f[v]+dist;
if(u!=Now) {
Belong[u]=BCC;
Circle[New].push_back(u);
}
if(u==Now&&v==Next)break;
}
for(int i=0; i<Circle[New].size(); i++) {
int Next=Circle[New][i];
AddEdge2(New,Next,min(abs(f[Next]-f[Now]),Length[BCC]-abs(f[Next]-f[Now])));
}
}
} else if((x!=(fa^1))&&Lowlink[Now]>Dfn[Next]) {
Lowlink[Now]=Dfn[Next];
S.push((Edge) {
Now,Next,e.dist
});
}
}
}

void Dfs(int Now,int fa,int depth,LL dist) {
Depth[Now]=depth;
Dist[Now]=dist;
First[Now]=++step;
p[Now][0]=fa;
for(int i=1; i<=20; i++)
if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
else break;
for(Edge& e:edges2[Now]) {
int Next=e.to;
Dfs(Next,Now,depth+1,dist+e.dist);
}
Last[Now]=step;
}

struct Cir {
int u;
LL d;
};

void TreeDp(int Now) {
Dist1[Now]=Dist2[Now]=0;
for(Edge& e:tree[Now]) {
int Next=e.to;
TreeDp(Next);
if(Dist1[Next]+e.dist>Dist1[Now]) { //所有转移都一样
Dist2[Now]=Dist1[Now];
Dist1[Now]=Dist1[Next]+e.dist;
} else if(Dist1[Next]+e.dist>Dist2[Now])Dist2[Now]=Dist1[Next]+e.dist;
}
if(Now>n) { //方点
deque<int>Q;
static vector<Cir>tmp;
tmp.clear();
Q.clear();
int NowBlock=Belong[tree[Now][0].to];
for(Edge& e:tree[Now])tmp.push_back((Cir) {e.to,f[e.to]});
for(Edge& e:tree[Now])tmp.push_back((Cir) {e.to,f[e.to]+Length[NowBlock]});
Q.push_back(0);
for(int i=1; i<tmp.size(); i++) {
while(!Q.empty()&&tmp[i].d-tmp[Q.front()].d>Length[NowBlock]/2)Q.pop_front();
if(!Q.empty())ans=max(ans,Dist1[tmp[i].u]+Dist1[tmp[Q.front()].u]+tmp[i].d-tmp[Q.front()].d);
while(!Q.empty()&&Dist1[tmp[Q.back()].u]-tmp[Q.back()].d<=Dist1[tmp[i].u]-tmp[i].d)Q.pop_back();
Q.push_back(i);
}
} else ans=max(ans,Dist1[Now]+Dist2[Now]);
tree[Now].clear(); //清空虚树
}

void build(vector<int>& a) {
int tmp=a.size();
for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
sort(a.begin(),a.end(),cmp);
auto it=unique(a.begin(),a.end());
a.erase(it,a.end());
static int top=0,S[maxn];
root=S[++top]=a[0];
for(int i=1; i<a.size(); i++) {
int now=a[i];
while(top>=1) {
if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
AddEdge3(S[top],now);
break;
}
top--;
}
if(S[top]!=now)S[++top]=now;
}
}

int main() {
int size=40<<20;
__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
memset(p,-1,sizeof(p));
New=n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
LL x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
Tarjan(1,-1);
step=0;
Dfs(1,-1,1,0);
q=Get_Int();
while(q--) {
int k=Get_Int();
a.clear();
for(int i=1; i<=k; i++)a.push_back(Get_Int());
sort(a.begin(),a.end(),cmp);
build(a);
ans=0;
TreeDp(root);
printf("%lld\n",ans);
}
exit(0);
}
姥爷们赏瓶冰阔落吧~
0%