P2993 [FJOI2014]最短路径树问题 最短路树+树分治

题目链接：https://www.luogu.com.cn/problem/P2993
题目大意：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+20, inf=1e9+1000;
const int maxn=300005;
struct edg{
    int to, w, next;
}e[N*4];

int tot, root, allnode, maxd;
int head[N], vis[N], siz[N];
int f[N];//求重心的最多子节点个数
void add(int u, int v, int w){
    e[tot].to=v, e[tot].next=head[u];
    e[tot].w=w, head[u]=tot++;
}
void getroot(int u, int fa){//求重心

    siz[u]=1;  f[u]=0;
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(to==fa||vis[to]){
            continue;
        }
        getroot(to, u);
        siz[u]+=siz[to];
        f[u]=max(f[u], siz[to]);
    }
    f[u]=max(allnode-siz[u], f[u]);
    if(f[u]<f[root]){
        root=u;
    }
}

int dis[N], s[N], num[N];
int ans=0, ans2=0, k;
void DFS(int u, int fa, int deep){//获取子树所有节点与根的距离并且更新最优解
    maxd=max(maxd, deep);//最大深度
    if(deep>k){
        return ;
    }
    int nowans=-1;
    if(s[k-1-deep]!=-1) nowans=dis[u]+s[k-1-deep];
    if(ans==nowans) ans2+=num[k-1-deep];//长度一样， 方案数++
    if(nowans>ans){                     //长度更长，更新
        ans=nowans; ans2=num[k-1-deep];
    }
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(to==fa||vis[to]){
            continue;
        }
        dis[to]=dis[u]+e[i].w;
        DFS(to, u, deep+1);
    }
}

void update(int u, int fa, int deep){//合并子树信息
    if(deep>k) return ;
    if(s[deep]==dis[u]) num[deep]++;//长度一样， 方案数++
    else if(dis[u]>s[deep]){        //长度更长，更新
        s[deep]=dis[u]; num[deep]=1;
    }
    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(to==fa||vis[to]){
            continue;
        }
        update(to, u, deep+1);
    }
}

void slove(int u){//以x为重心进行计算
    maxd=0; vis[u]=1;
    for(int i=head[u]; i!=-1; i=e[i].next){//所有子树贡献
        int to=e[i].to;
        if(vis[to]){
            continue;
        }
        dis[to]=e[i].w;
        DFS(to, u, 1);
        update(to, u, 1);//合并s[]和num[]
    }
    for(int i=1; i<=maxd; i++) s[i]=-1, num[i]=0;
    s[0]=0, num[0]=1;// root的影响

    for(int i=head[u]; i!=-1; i=e[i].next){
        int to=e[i].to;
        if(vis[to]){
            continue;
        }
        allnode=siz[to];//继续分治
        root=0; getroot(to, u);
        slove(root);
    }

}

struct Tree{

    int m, dis[maxn], vis[maxn], pre[maxn], preb[maxn], cut=0, cutg=0;

    struct node{
        int to, w, next, id;
    }e[maxn*2];
    int head[maxn];
    Tree(){
        memset(head, -1, sizeof(head)); cut=0;
        memset(dis, 0x7f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
    }
    void addcut(int u,int v, int w, int id=0){
        e[cut].to=v,e[cut].w=w,e[cut].id=id, e[cut].next=head[u],head[u]=cut++;
    }
    priority_queue<pair<int, int> > q;
    void dijkstra(int s, int t){
        q.push({0, s}); dis[s]=0;
        while(!q.empty()){
            pair<int, int> pos=q.top(); q.pop();
            if(vis[pos.second]) continue;
            vis[pos.second]=1;
            for(int i=head[pos.second];i>=0;i=e[i].next){
                if(!vis[e[i].to]&&dis[e[i].to]>dis[pos.second]+e[i].w){
                    dis[e[i].to]=dis[pos.second]+e[i].w;
                    pre[e[i].to]=pos.second; preb[e[i].to]=e[i].w;//保存前驱节点， 和边的编号
                    q.push({-dis[e[i].to], e[i].to});
                }
            }
        }
    }
    void getTree(int n){
        dijkstra(1, n);
        for(int i=2; i<=n; i++){//存储G图最短路树
            //cout<<i<<"-"<<pre[i]<<endl;
            add(pre[i], i, preb[i]);
            add(i, pre[i], preb[i]);
        }
    }
}tree;

int main(){

    int n, m, u, v, w;
    while(scanf("%d%d%d", &n, &m, &k)!=EOF){
        memset(head, -1, sizeof(head));
        memset(vis, 0, sizeof(vis));
        memset(s, -1, sizeof(s));
        memset(num, 0, sizeof(num));
        s[0]=0, num[0]=1;
        tot=1;

        for(int i=1; i<=m; i++){
            scanf("%d%d%d", &u, &v, &w);
            tree.addcut(u, v ,w), tree.addcut(v, u, w);
        }
        tree.getTree(n);

        root=ans=ans2=0;
        allnode=n, f[0]=inf;
        getroot(1, 0);
        slove(root);
        printf("%d %d\n", ans, ans2);

    }

    return 0;
}