bzoj 4016: [FJOI2014]最短路径树问题

这题很显然直接最短路（蒟蒻只会spfa）搞出树，点分治就好，，然而不知道为什么不对。。（本机手动和AC代码对拍了一下没什么问题的样子。。。）

挖坑++

#include <bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f 
#define N 30005
using namespace std;
inline int ra()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct edge
{
    int next,to,v;
}e[N<<2];
int head[N],cnt;
int from[N],dis[N],val[N],q[N<<3];
bool inq[N],vis[N],can[N];
int n,m,k,mx_len,MAX,ans,root,sz;
int depth[N];
int size[N];
map<int ,int > sum;
void insert(int x, int y, int v)
{
    e[++cnt].next=head[x]; e[cnt].to=y; e[cnt].v=v; head[x]=cnt;
}
void spfa()
{
    for (int i=1; i<=n; i++) dis[i]=inf;
    int l=0,r=1; q[0]=1; dis[1]=0; inq[1]=1;
    while (l<r)
    {
        int x=q[l++]; 
        for (int i=head[x];i;i=e[i].next)
        {
            if (dis[e[i].to]==dis[x]+e[i].v && from[e[i].to]>x)
            {
                from[e[i].to]=x;
                val[e[i].to]=e[i].v;
            }
            if (dis[e[i].to]>dis[x]+e[i].v)
            {
                dis[e[i].to]=dis[x]+e[i].v;
                from[e[i].to]=x;
                val[e[i].to]=e[i].v;
                if (!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    q[r++]=e[i].to;
                }
            }
        }
        inq[x]=0;
    } 
}
void build_tree()
{
    cnt=0; memset(head,0,sizeof(head));
    for (int i=1; i<=n; i++)
    {
        if (!vis[i])
        {
            while (i)
            {
                if (vis[i]) break;
                insert(from[i],i,val[i]);
                insert(i,from[i],val[i]);
                vis[i]=1;
                i=from[i];
            }
        }
    }
}
void get_root(int x, int fa)
{
    size[x]=1;
    int mx=0;
    for (int i=head[x];i;i=e[i].next)
    {
        if (can[e[i].to] || e[i].to==fa) continue;
        get_root(e[i].to,x);
        mx=max(mx,size[e[i].to]);
        size[x]+=size[e[i].to];
    }
    mx=max(mx,sz-size[x]);
    if (mx<MAX) MAX=mx,root=x;
}
void get_len(int x, int fa, int len, int deep)
{
    mx_len=max(mx_len,depth[k-len]+deep);
    for (int i=head[x];i;i=e[i].next)
    {
        if (e[i].to==fa || can[e[i].to]) continue;
        get_len(e[i].to,x,len+1,deep+e[i].v);
    }
}
void add_len(int x, int fa, int len, int deep)
{
    depth[len]=max(depth[len],deep);
    for (int i=head[x];i;i=e[i].next)
    {
        if (e[i].to==fa || can[e[i].to]) continue;
        add_len(e[i].to,x,len+1,deep+e[i].v);
    }
}
void clear_len(int x, int fa, int len)
{
    depth[len]=0;
    for (int i=head[x];i;i=e[i].next)
    {
        if (e[i].to==fa || can[e[i].to]) continue;
        clear_len(e[i].to,x,len+1);
    }
}
void solve_len(int x)
{
    MAX=n; sz=size[x]?size[x]:n; get_root(x,0); can[root]=1;
    for (int i=head[root];i;i=e[i].next)
    {
        if (can[e[i].to]) continue;
        get_len(e[i].to,root,1,e[i].v);
        add_len(e[i].to,root,1,e[i].v);
    }
    for (int i=head[root];i;i=e[i].next)
        if (!can[e[i].to]) clear_len(e[i].to,root,1);
    for (int i=head[root];i;i=e[i].next)
    {
        if (can[e[i].to]) continue;
        solve_len(e[i].to);
    }
}
void get_ans(int x, int fa, int deep)
{
    ans+=sum[mx_len-deep];
//    if (sum[mx_len-deep]){cout<<x<<"  "<<sum[mx_len-deep]; system("pause");}
    for (int i=head[x];i;i=e[i].next)
    {
        if (can[e[i].to] || e[i].to==fa) continue;
        get_ans(e[i].to,x,deep+e[i].v);
    }
}
void add_ans(int x, int fa, int deep)
{
    sum[deep]++;
    for (int i=head[x];i;i=e[i].next)
    {
        if (fa==e[i].to || can[e[i].to]) continue;
        add_ans(e[i].to,x,deep+e[i].v);
    }
}
void clear_ans(int x, int fa, int deep)
{
    sum[deep]=0;
    for (int i=head[x];i;i=e[i].next)
    {
        if (fa==e[i].to || can[e[i].to]) continue;
        clear_ans(e[i].to,x,deep+e[i].v);
    }
}
void final_solve(int x)
{
    MAX=n; sz=size[x]?size[x]:n; 
    get_root(x,0); can[root]=1;
//    cout<<root;system("pause");
    for (int i=head[root];i;i=e[i].next)
    {
        if (can[e[i].to]) continue;
        get_ans(e[i].to,root,e[i].v);
        add_ans(e[i].to,root,e[i].v);
    }
    for (int i=head[root];i;i=e[i].next)
        if (!can[e[i].to]) clear_ans(e[i].to,root,e[i].v);
    for (int i=head[root];i;i=e[i].next)
    {
        if (can[e[i].to]) continue;
        final_solve(e[i].to);
    }
}    
int main(int argc, char const *argv[])
{
//    freopen("bzoj4016.in","r",stdin);
    n=ra(); m=ra(); k=ra(); k--;
    for (int i=1; i<=m; i++) 
    {
        int x=ra(),y=ra(),v=ra();
        insert(x,y,v);
        insert(y,x,v);
    }
    spfa();
    build_tree();
    can[0]=1;    solve_len(1);
    memset(can,0,sizeof(can)); can[0]=1;
    memset(size,0,sizeof(size));
    final_solve(1);
    cout<<mx_len<<" "<<ans<<endl;
    return 0;
}