点分治问题 ----------- P2993 [FJOI]最短路径树问题 [最短路径树+点分治+采坑]

题目链接

解题思路：

首先我们知道最小路径树实际上就是Dijkstra算法在找最短路的时候转移的过程就是一个最短路径树。

那么我们就可以先跑个最短路，记录一下各个最短路的路径。然后就是很裸的点分治。分治根节点，枚举每个子树和前面统计过的子树的贡献，计算完一个子树后，更新每个深度下的最长路径，以及路径条数。

但是这个题目问的有问题，实际上它那个路径条数是在K的限制下的条数。

坑点：

1.就是对于分治时候枚举子树的时候，他可以直接从分治的root连到子树，不需要其他子树，也就是deepth==k−1deepth == k - 1deepth==k−1的情况。

2.就是在更新答案的时候我们还要判断一下这个深度的结点是否存在？。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 6e4 + 10;struct node {int nxt, to, w;}edge[maxn<<1],edge1[maxn<<1];int head[maxn],head1[maxn], cnt = 1, cnt1 = 1;inline void add(int from, int to, int val) {//建图edge[++cnt] = {head[from],to,val};head[from] = cnt; }inline void add1(int from, int to, int val) {//建最小路径树edge1[++cnt1] = {head1[from],to,val};head1[from] = cnt1;}int n, m, k;//.......... 点分治bool vis[maxn];int MX, root, max_son[maxn], now_num ,siz[maxn];void getroot(int u, int fa) {max_son[u] = 0;siz[u] = 1; for(int i = head1[u]; i; i = edge1[i].nxt) {int v = edge1[i].to;if(v == fa || vis[v]) continue;getroot(v,u);siz[u] += siz[v];max_son[u] = max(max_son[u],siz[v]);}max_son[u] = max(max_son[u],now_num - siz[u]);if(max_son[u] < MX) MX = max_son[u], root = u; }int kpath, Count;pair<int,int> maxk[maxn];//长度为i的最长路径的长度，以及条数int maxdep;void dfs(int u, int fa, int dep, int len) {maxdep = max(maxdep,dep);if(dep == k - 1) {//在自己子树进行统计 特判if(len == kpath) Count ++;else if(len > kpath){kpath = len;Count = 1;}return;}//maxk[k-dep-1].first == 0 说明没有这个点if(maxk[k-dep-1].first && kpath < maxk[k-dep-1].first + len) {kpath = maxk[k-dep-1].first + len;Count = maxk[k-dep-1].second;} else if(maxk[k-dep-1].first && kpath == maxk[k-dep-1].first + len)Count += maxk[k-dep-1].second;for(int i = head1[u]; i; i = edge1[i].nxt) {int v = edge1[i].to;if(vis[v] || v == fa) continue;dfs(v,u,dep+1,len+edge1[i].w);}}void dfs1(int u, int fa, int dep, int len) {if(maxk[dep].first < len) maxk[dep] = {len,1};else if(maxk[dep].first == len) maxk[dep].second++;for(int i = head1[u]; i; i = edge1[i].nxt) {int v = edge1[i].to;if(vis[v] || v == fa) continue;dfs1(v,u,dep+1,len+edge1[i].w);}}inline void getans(int u) {maxdep = 0;for(int i = head1[u]; i; i = edge1[i].nxt) {int v = edge1[i].to;if(vis[v]) continue;dfs(v,u,1,edge1[i].w);dfs1(v,u,1,edge1[i].w);}for(int i = 0; i <= maxdep; ++ i)maxk[i] = {0,0};}void Div(int u) {vis[u] = 1;getans(u);for(int i = head1[u]; i; i = edge1[i].nxt) {int v = edge1[i].to;if(vis[v]) continue;MX = 1e9, root = 0;now_num = siz[v];getroot(v,u);Div(root);}}//..................................int dist[maxn];pair<int,int> path[maxn];bool f[maxn];void Dij(int start) {memset(dist,0x3f,sizeof(dist));dist[start] = 0;priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > q;q.push((pair<int,int>){0,start});while(!q.empty()) {auto top = q.top();q.pop();if(f[top.second]) continue;f[top.second] = true;for(int i = head[top.second]; i; i = edge[i].nxt) {int v = edge[i].to;if(dist[v] > dist[top.second] + edge[i].w) {path[v] = {top.second,edge[i].w};dist[v] = dist[top.second] + edge[i].w;q.push((pair<int,int>){dist[v],v});}}}}void build() {for(int i = 1; i <= n; ++ i) if(path[i].first) {add1(i,path[i].first,path[i].second);add1(path[i].first,i,path[i].second);} }//................................int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//.........cin >> n >> m >> k;for(int i = 0; i < m; ++ i) {int u, v, w;cin >> u >> v >> w;add(u,v,w);add(v,u,w);}Dij(1);build();now_num = n, MX = 1e9, root = 0;getroot(1,0);Div(root);cout << kpath << " " << Count << "\n";return 0;}

如果觉得《点分治问题 ----------- P2993 [FJOI]最短路径树问题 [最短路径树+点分治+采坑]》对你有帮助，请点赞、收藏，并留下你的观点哦！