# P2993 [fjoi2014] shortest path tree problem (Dijkstra & point divide and conquer)

2021-08-10 08:44:10

P2993 [FJOI2014] The shortest path tree problem (dijkstra& Point divide and conquer )

Ideas

part1

run dijkstra, Then sort the edges , Establish the shortest path spanning tree MPT

part2

Naked dots divide , The path length and number of edges of a subtree are preprocessed each time , Then use two side buckets to maintain ( The path is long , Number of paths ) Just two variables .

Time complexity ： O ( m l o g n + n l o g 2 n ) O(mlogn+nlog^2n) O(mlogn+nlog2n)

code

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=3e4+5,M=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define hh(u,i) for(int i=h[u];i;i=e[i].nt)
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
int n,m,k;
//if have char input #define should cancel
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
vector<PII>g[N];
int d[N],vis[N];
void dij(){
priority_queue<PII>q;mst(d,0x3f);d[1]=0;q.push({0,1});
while(!q.empty()){
int u=q.top().se,l=-q.top().fi;q.pop();
if(l>d[u]) continue;
for(auto [v,w]:g[u]){
if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({-d[v],v});
}
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
}
int h[N],cnt;
struct edge{
int to,nt,w;
}e[M<<1];
e[++cnt]={v,h[u],w},h[u]=cnt;
e[++cnt]={u,h[v],w},h[v]=cnt;
}
//create MPT mininum path tree
void bud(int u){
vis[u]=1;
for(auto [v,w]:g[u]){
if(vis[v]||d[v]!=d[u]+w) continue;
}
}
int sz[N],mx[N],rt,sum;
void grt(int u,int fa){
mx[u]=0,sz[u]=1;
hh(u,i){
int v=e[i].to,w=e[i].w;
if(vis[v]||v==fa) continue;
grt(v,u);
sz[u]+=sz[v];mx[u]=max(mx[u],sz[v]);
}
mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt]) rt=u;
}
int tot;
PII dis[N],tmp[N],now[N];
PII ans;
int bkz;
void dfs(int u,int fa,int x,int y){
if(y<k) dis[++tot]={x,y};
hh(u,i){
int v=e[i].to,w=e[i].w;
if(vis[v]||v==fa) continue;
dfs(v,u,x+w,y+1);
}
}
void cal(int u,int x,int y){
tot=0;dfs(u,0,x,y);
for(int i=1;i<=tot;i++){
auto [x,y]=dis[i];//w len
int z=k-1-y;
auto [p,q]=tmp[z]; //w cnt
if(x+p>ans.fi) ans={x+p,q};
else if(x+p==ans.fi) ans.se+=q;
}
for(int i=1;i<=tot;i++){
auto [x,y]=dis[i];
auto [p,q]=tmp[y];
if(x>p) tmp[y]={x,1};
else if(x==p) tmp[y].se++;
bkz=max(bkz,x);
}
}
void solve(int u){
vis[u]=1;
tmp[0]={0,1};bkz=0;
hh(u,i){
int v=e[i].to,w=e[i].w;
if(!vis[v]) cal(v,w,1);
}
memset(tmp,0,sizeof(PII)*(bkz+2));
hh(u,i){
int v=e[i].to;if(vis[v]) continue;
sum=mx[rt=0]=sz[v];grt(v,u);grt(rt,0);
solve(rt);
}
}
int main(){
for(int i=1,u,v,w;i<=m;i++){
g[u].pb(v,w);
g[v].pb(u,w);
}
dij();bud(1),mx[0]=sum=n;mst(vis,0);
grt(1,0);grt(rt,0);
solve(rt);
printf("%d %d\n",ans.fi,ans.se);
return 0;
}
```

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.
```

https://chowdera.com/2021/08/20210810084311898I.html