首页 > 代码库 > BZOJ 3124 直径

BZOJ 3124 直径

计算去掉每一条边之后的直径。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 200500#define maxe 400500using namespace std;struct edge{    long long v,w,mx,nxt;}e[maxe];int t,n,x,y,z,g[maxv],nume=1,root;int fath_e[maxv],son[maxv],pos;long long val1[maxv],val2[maxv],ans=0,dis[maxv],ret=0,dr=0;inline int read(){    int data=http://www.mamicode.com/0;char ch;    while (ch<0 || ch>9)        ch=getchar();    while (ch>=0 && ch<=9)    {        data=data*10+ch-0;        ch=getchar();    }    return data;}inline void reset1(){    memset(g+1,0,n*sizeof(int));    ans=0;nume=1;ret=0;}inline void reset2(){    memset(son+1,0,n*sizeof(int));}inline void addedge(int u,int v,int w){    e[++nume].v=v;    e[nume].w=w;    e[nume].mx=0;    e[nume].nxt=g[u];    g[u]=nume;}void dfs1(int x,int fath){    for (int i=g[x];i;i=e[i].nxt)    {        int v=e[i].v;        if (v!=fath)        {            dis[v]=dis[x]+e[i].w;            if (dis[v]>ret) {ret=dis[v];root=v;}            dfs1(v,x);        }    }}void dfs2(int x,int fath){    val1[x]=val2[x]=0;long long fx=0,sx=0;    for (int i=g[x];i;i=e[i].nxt)    {        int v=e[i].v;        if (v!=fath)        {            dis[v]=dis[x]+e[i].w;fath_e[v]=i;            dfs2(v,x);            if (val2[v]+e[i].w>fx) {sx=fx;fx=val2[v]+e[i].w;son[x]=v;}            else if (val2[v]+e[i].w>sx) sx=val2[v]+e[i].w;            val1[x]=max(val1[x],val1[v]);        }    }    val2[x]=fx;    val1[x]=max(val1[x],fx+sx);}inline void get_labled(int type){    int now=son[root];long long regis=0;    while (now)    {        e[fath_e[now]].mx=max(e[fath_e[now]].mx,val1[now]);        e[fath_e[now]^1].mx=max(e[fath_e[now]^1].mx,val1[now]);        if (type==2)             if (e[fath_e[now]].mx!=dr)                 ans++;        ret++;pos=now;now=son[now];    }}inline void work(){    reset1();    n=read();    for (register int i=1;i<=n-1;i++)    {        x=read();y=read();z=read();        addedge(x,y,z);addedge(y,x,z);    }    ret=0;    dfs1(1,1);    reset2();dis[root]=0;fath_e[root]=0;    dfs2(root,root);    ret=0;dr=val1[root];    get_labled(1);    reset2();root=pos;dis[root]=0;fath_e[root]=0;    dfs2(root,root);    get_labled(2);    printf("%lld\n%lld\n",dr,ans);}int main(){    work();    return 0;}

 

BZOJ 3124 直径