The main idea of the title
give one
n
n
An unrooted tree with n nodes, each edge has an edge weight.
w
i
w_i
wi?. make
d
i
s
(
x
,
y
)
dis(x,y)
dis(x,y) is a point
x
x
x to point
y
y
y distance.
You need to maintain an initially empty set of point pairs
S
S
S, yes
m
m
m operations, each operation has two types:
1 a bTowardsS
S
Insert point pair in S
(
a
,
b
)
(a,b)
(a,b)
2 x yQuery the following formula and output the result
min
?
(
a
,
b
)
∈
S
d
i
s
(
x
,
a
)
+
d
i
s
(
y
,
b
)
\min\limits_{(a,b)\in S}dis(x,a) + dis(y,b)
(a,b)∈Smin?dis(x,a) + dis(y,b)
If querying
S
S
If S is empty, output
?
1
-1
?1.
1
≤
n
,
m
≤
2
×
1
0
5
,
1
≤
w
i
≤
1
0
9
1\leq n,m\leq 2\times 10^5,1\leq w_i\leq 10^9
1≤n,m≤2×105,1≤wi?≤109
in subtask
2
2
2 in,
b
=
1
b=1
b=1.
time limit
4000
m
s
4000ms
4000ms, space limit
512
M
B
512MB
512MB.
Solution
First, we consider subtasks
2
2
2. At this time, it is equivalent to the point pair becoming a single point. The problem becomes to insert a point into the point set each time, or to ask the distance of the nearest point to a certain point.
Consider using a point-by-point tree. At each center of gravity, just maintain the point closest to the center of gravity in the point-by-point tree. Just keep jumping up when modifying and querying. The time complexity is
O
(
n
log
?
n
)
O(n\log n)
O(nlogn).
Let’s consider how to deal with the point pair situation.
We can take all operations offline and put
a
i
a_i
ai?and
x
i
x_i
xi? Perform point divide and conquer, and process all
a
i
a_i
ai?and
x
i
x_i
xi?The operation in its point divide and conquer subtree. Let the current dividing and conquering center be the point
u
u
u, then insert into another point tree in chronological order
b
i
b_i
bi?, and add
d
i
s
(
u
,
a
i
)
dis(u,a_i)
dis(u,ai?), when querying, just use the operation query using ordinary point tree (that is, keep jumping up).
Each modification and query will be done in a point-and-conquer process.
O
(
log
?
n
)
O(\log n)
It is reflected in O(logn) points, and each reflection must be on the point tree.
O
(
log
?
n
)
O(\log n)
O(logn) to modify and query, so the total time complexity is
O
(
m
log
?
2
n
)
O(m\log^2n)
O(mlog2n).
You can refer to the code to help understand.
code
#include<bits/stdc + + .h>
using namespace std;
const int N=200000;
int n,m,fl=0,root,rt=0,tot=0,d[2*N + 5],l[2*N + 5],r[N + 5];
int siz[N + 5],mxd[N + 5],z[N + 5],fa[N + 5],dw[N + 5];
long long w[2*N + 5],mn[N + 5],ans[N + 5],dis[N + 5][20];
struct que{<!-- -->
int op,x,y;
}q[N + 5];
vector<int>G[N + 5],id[N + 5];
void add(int xx,int yy,int zz){<!-- -->
l[ + + tot]=r[xx];d[tot]=yy;r[xx]=tot;w[tot]=zz;
}
void dfs(int u,int fa,int all,int dw){<!-- -->
siz[u]=1;mxd[u]=0;mn[u]=1e18;
for(int i=r[u];i;i=l[i]){<!-- -->
if(d[i]==fa||z[d[i]]) continue;
dis[d[i]][dw]=dis[u][dw] + w[i];
dfs(d[i],u,all,dw);
siz[u] + =siz[d[i]];
mxd[u]=max(mxd[u],siz[d[i]]);
}
mxd[u]=max(mxd[u],all-siz[u]);
if(mxd[u]<mxd[rt]) rt=u;
}
void dd(int u){<!-- -->
z[u]=1;
for(int i=r[u];i;i=l[i]){<!-- -->
if(z[d[i]]) continue;
rt=0;
dis[d[i]][dw[u]]=w[i];
dfs(d[i],0,siz[d[i]],dw[u]);
G[u].push_back(rt);fa[rt]=u;
dw[rt]=dw[u] + 1;
dd(rt);
}
}
void pt(int x,long long v){<!-- -->
for(int tx=x;tx;tx=fa[tx]){<!-- -->
mn[tx]=min(mn[tx],v + dis[x][dw[tx]]);
}
}
long long gt(int x){<!-- -->
long long re=1e18;
for(int tx=x;tx;tx=fa[tx]){<!-- -->
re=min(re,mn[tx] + dis[x][dw[tx]]);
}
return re;
}
void clr(int x){<!-- -->
for(int tx=x;tx;tx=fa[tx]) mn[tx]=1e18;
}
void solve(int u){<!-- -->
for(int i:id[u]){<!-- -->
if(q[i].op==1) pt(q[i].y,dis[q[i].x][dw[u]]);
else ans[i]=min(ans[i],gt(q[i].y) + dis[q[i].x][dw[u]]);
}
for(int i:id[u]){<!-- -->
if(q[i].op==1) clr(q[i].y);
}
for(int v:G[u]) solve(v);
}
int main()
{<!-- -->
freopen("distance.in","r",stdin);
freopen("distance.out","w",stdout);
scanf("%d%d", & amp;n, & amp;m);
for(int i=1,x,y,z;i<n;i + + ){<!-- -->
scanf("%d%d%d", & amp;x, & amp;y, & amp;z);
add(x,y,z);add(y,x,z);
}
for(int i=1;i<=m;i + + ){<!-- -->
scanf("%d%d%d", & amp;q[i].op, & amp;q[i].x, & amp;q[i].y);
ans[i]=1e18;
}
mxd[0]=1e9;dfs(1,0,n,0);
root=rt;dw[root]=1;dd(root);
for(int i=1;i<=m;i + + ){<!-- -->
for(int u=q[i].x;u;u=fa[u]) id[u].push_back(i);
}
solve(root);
for(int i=1;i<=m;i + + ){<!-- -->
if(q[i].op==1) fl=1;
else{<!-- -->
if(!fl) printf("-1\\
");
else printf("%lld\\
",ans[i]);
}
}
return 0;
}