BZOJ3784 树上的路径

题面:

​ 给你一棵n个节点的树,有边权,问树上所有点对的距离中,最大的M个是多少。

http://www.lydsy.com/JudgeOnline/problem.php?id=3784

题解

解题分析

​ 鉴于N=50000N=50000,M<=300000M<=300000,直接把所有点对求出来是不现实的。

​ 不妨我们得到了某些点对的LCA是ii,那么其它点到ii的距离我们可以求得,为了不重复计算,对于每一个点,它在满足LCA是i的情况下,一定是在已经完全访问过的子树中取一个距离最大的。

​ 更确切的说,满足当前点是这个点,满足LCALCAii,再满足不重复计算的情况下,它能够决策的区间是前面所有子树(包括ii),那么我们可以通过dfsdfs序把它变成一个序列,也就是对于某一个点,要查询前面某一段区间的disdis的最大值,同时维护最大值。

​ 这个可以用类似NOI超级钢琴的做法。

​ 同理,我们推出了点分治的思路。

​ 每次对于分治中心,得到其子树的所有disdis,依次访问每一棵子树,把dfsdfs序延续扩展下去,得到所谓的点分序

​ 然后序列上的每一个数都表示了在LCA和节点不同的情况下的某个点,那么它的可以决策的节点必然是连续的前面一段区间。

​ 现在,问题真正转化成了区间问题。区间最值可以用rmqrmq来实现O(1)O(1)查询。

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
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<bitset>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<ctime>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
#define pc putchar
#define RG register
char __wzp[1<<15|1],*__S=__wzp+32768;
#ifdef LOCAL
#define gc() getchar()
#else
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
#endif
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
const int oo = 0x3f3f3f3f,inf = oo;
#define mem(x,v) memset(x,v,sizeof(x))
#define sqr(x) ((x)*(x))
#define lowbit(x) (x&-x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define wait system("pause")
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define file(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define writeln(x) printf("%d\n",x);
#define N 50009
struct Edge{
int to,nxt,dist;
Edge(){}
Edge(int to,int nxt,int dist):to(to),nxt(nxt),dist(dist){}
}edge[2*N];
int first[N],nume;
int Mx[N],size[N],rt;
bool vis[N];
int sum;
int tot,L[N*20],R[N*20],f[N*20];
void Addedge(int a,int b,int c){
edge[nume] = Edge(b,first[a],c);
first[a] = nume++;
}
void getrt(int u,int fa){
int e,v;
size[u]=1;Mx[u]=0;
for (e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(v == fa || vis[v]) continue;
getrt(v,u);
size[u]+=size[v];
Mx[u]=max(Mx[u],size[v]);
}
Mx[u]=max(Mx[u],sum-size[u]);
if(Mx[u]<Mx[rt])rt=u;
}
int l,r;
void getdis(int u,int fa,int w){
++tot;
f[tot] = w;L[tot] = l;R[tot] = r;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(v == fa || vis[v]) continue;
getdis(v,u,w + edge[e].dist);
}
}
void solve(int u){
vis[u] = true;
l = r = ++tot;f[tot] = 0;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(!vis[v]) getdis(v,u,edge[e].dist),r=tot;
}
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(!vis[v]){
sum = size[v];
rt = 0;
getrt(v,u);
solve(rt);
}
}
}
int Log[N*20],rmq[N*20][20];
void initrmq(){
Log[0] = -1;
for (int i=1;i<=tot;i++) Log[i] = Log[i>>1] + 1;
for (int i=1;i<=tot;i++) rmq[i][0] = i;
for (int j=1;j<=20;j++)
for (int i=1;i+(1<<j)-1<=tot;i++){
int r1 = rmq[i][j-1],r2 = rmq[i+(1<<(j-1))][j-1];
rmq[i][j] = f[r1]>f[r2]? r1 : r2;
}
}
int query(int l,int r){
int t = Log[r-l+1];
int r1 = rmq[l][t],r2 = rmq[r-(1<<t)+1][t];
return f[r1]>f[r2] ? r1 : r2;
}
struct Node{
int i,l,r,x;
bool operator < (const Node &a) const{
return f[i]+f[x]<f[a.i]+f[a.x];
}
};
priority_queue<Node> Q;
int n,m;
int main(){
n=read(),m=read();
mem(first,-1);nume = 0;
rep(i,1,n){
int a = read(),b = read(),c = read();
Addedge(a,b,c);
Addedge(b,a,c);
}
mem(vis,false);
Mx[0]=inf;
sum=n;
rt=0;
getrt(1,-1);
solve(rt);
initrmq();
for (int i=1;i<=tot;i++)
if(L[i]<=R[i])
Q.push((Node){i,L[i],R[i],query(L[i],R[i])});
while(m--){
Node u = Q.top();Q.pop();
printf("%d\n",f[u.i]+f[u.x]);
if(u.l<=u.x-1) Q.push((Node){u.i,u.l,u.x-1,query(u.l,u.x-1)});
if(u.x+1<=u.r) Q.push((Node){u.i,u.x+1,u.r,query(u.x+1,u.r)});
}
return 0;
}
文章目录
  1. 1. 题面:
  2. 2. 题解