题目大意：

找基环树直径

（这个题输入给出的是内向基环树（虽然是无向边））

 

存在两种情况：

1.直径在树上。

2.直径从树里走到环上，再走进另外一个树里。

 

首先dfs找到环。

第一种直接树形dp。dp[i]i往下最长路径。还能用来求第二种情况。

第二种，找到环之后，断环成链，复制一倍。求的是，选择距离小于环长的两个点，贡献是两个点的dp[i],和两个点之间的距离。这个用单调队列优化dp即可。

 

bzoj会爆栈mmp

如果你是ywy可以bfs求树形dp

其实，这是一个内向基环树，所以，直接topo排序，从叶子往上面topo

即可求得dp，还能求得环。

 

代码：（dfs爆栈版）

#pragma comment(linker, "/STACK:102400000,102400000")#include
     
      #define il inline#define reg register int #define numb (ch^'0')using namespace std;typedef long long ll;void rd(int &x){    char ch;x=0;    while(!isdigit(ch=getchar()));    for(x=numb;isdigit(ch=getchar());x=x*10+numb);}namespace Miracle{const int N=1e6+5;int n;struct node{    int nxt,to;    ll val;}e[2*N];int hd[N],cnt=1;void add(int x,int y,int z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].val=z;    hd[x]=cnt;}bool vis[N];bool on[N];//on the huanbool in[N];int to[N],v[N];int sta[N],top;int len;//huan changint mem[2*N],tot;ll cos[2*N];int q[2*N],l,r;ll f[N];ll ans;ll sum;ll zhi;bool fl;void dfs(int x,int in_edge){//    cout<<" dfs "<
      
       <<" "<
       
        <<" "<
        
         <
         
          =len) ++l;        if(i!=1) sum=max(sum,f[mem[q[l]]]-cos[q[l]]+cos[i]+f[mem[i]]);        while(l<=r&&f[mem[q[r]]]-cos[q[r]]<=f[mem[i]]-cos[i]) --r;        q[++r]=i;    }    return sum;}int main(){    rd(n);int x;int z;    for(reg i=1;i<=n;++i){        rd(x);rd(z);        to[i]=x;        v[i]=z;        add(i,x,z);add(x,i,z);    }    for(reg i=1;i<=n;++i){        if(!vis[i]){            ans+=wrk(i);        }    }    printf("%lld",ans);    return 0;}}int main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2018/11/4 9:27:26*/