bzoj 1791, P4381 - [IOI 2008] Island [기 환 수, 나무형 dp, 단조 로 운 대열 dp, 나무의 직경]

본론
평가 기록:https://www.luogu.org/recordnew/lists?uid=52918&pid=P4381
제목 의 대의
n 개의 섬 이 있 고 n 개의 방향 이 없다.지나 가 는 길 과 섬 은 다시 가면 안 되 고 배 를 탈 수 있다.배 를 타 는 것 은 이전에 사용 하지 않 았 던 배 와 도로 가 그 지점 에 도착 해 야 배 를 탈 수 있다 고 요구한다.
최 장 을 구하 면 얼마나 멀리 갈 수 있 습 니까?
문제 풀이 의 사고 방향.
우선 이것 은 기 환 나무 숲 으로 배 를 타 는 규정 에 따라 사실은 모든 기 환 나 무 는 한 번 만 걸 을 수 있다 는 것 이다.이때 우 리 는 답 이 모든 기 환 나무의 지름 의 합 이라는 것 을 알 수 있다.그런 후에 우 리 는 지름 을 어떻게 계산 할 것 인 가 를 고려 했다.
고 리 를 뿌리 로 삼다.우 리 는 답 이 두 가지 만 가능 하 다 는 것 을 발견 했다.
경과 근
뿌리 를 거치 지 않다.
우 리 는 뿌리 를 거치 지 않 고 f x f 를 계산 하 는 것 을 고려 합 니 다.x fx (f x f x fx 는 x 서브 트 리 에서 x 에서 가장 먼 점 의 거 리 를 나타 낸다) 그리고 나무의 지름 을 구 하 는 방법 으로 뿌리 아래 의 모든 나무의 지름 을 구하 고 기록 합 니 다.그리고 우 리 는 뿌리 를 거 친 것 을 계산한다.링 의 노드 가 s s 집합 이 라 고 가정 하면 정 답 은 m a x (f s i + f s j + d i s i ∼ j) max (f {s i} + f {s j} + dis {i \ sim j}) max (fsi + fsj + disi ∼ j) dis 는 링 위의 i 에서 j 까지 의 가장 먼 거 리 를 나타 낸다.우 리 는 단조 로 운 대기 열 dp 를 통 해 답 을 계산 해 낼 수 있다.
code

#include
#include
#include
#include
#define N 1000010
#define lls long long
using namespace std;
struct node{
    int to,next,w;
}a[2*N];
int n,x,y,tot,t;
lls ls[N],in[N],cr[2*N],v[N],k[N],f[N],d[N],dis[2*N],ans,q[2*N];
void addl(int x,int y,int w)//  
{
    a[++tot].to=y;
    a[tot].w=w;
    a[tot].next=ls[x];
    ls[x]=tot;
    in[y]++;
}
void dfs(int now,int k){
    v[now]=k;
    for (int i=ls[now];i;i=a[i].next){
        int y=a[i].to;
        if(!v[y]) dfs(y,k);
    }
}//     
void topsort(){
	int l=0,r=0;
    for (int i=1;i<=n;i++) 
	  if(in[i]==1) q[++r]=i;
    while(l<r) {
        int now=q[++l];
        for (int i=ls[now];i;i=a[i].next){
            int y=a[i].to;
            if(in[y]>1){
                in[y]--;
                d[v[now]]=max(d[v[now]],f[now]+f[y]+a[i].w);
                f[y]=max(f[y],f[now]+a[i].w);
                if(in[y]==1) q[++r]=y;
            }
        }
    }
}//      
void dp(int t,int x){
    int m=0,y=x,i;
    do{
        cr[++m]=f[y];in[y]=1;
        for(i=ls[y];i;i=a[i].next){
            if(in[a[i].to]>1){
                dis[m+1]=dis[m]+a[i].w;
                y=a[i].to;
                break;
            }
        }
    }while(i);//       
    if(m==2){
        int l=0;
        for (int i=ls[y];i;i=a[i].next) 
            if(a[i].to==x) l=max(l,a[i].w);
        d[t]=max(d[t],f[x]+f[y]+l);
        return;
    }//  
    for(int i=ls[y];i;i=a[i].next){
        if(a[i].to==x) {
            dis[m+1]=dis[m]+a[i].w;
            break;
        }
    }//    
    for (int i=1;i<=m;i++){
            cr[i+m]=cr[i];
            dis[m+i]=dis[m+1]+dis[i];
    }//        
    int l=1,r=0;
    q[++r]=1;
    for (int i=2;i<2*m;i++){
        while(l<=r&&i-q[l]>=m)
          l++;
        d[t]=max(dis[i]-dis[q[l]]+cr[i]+cr[q[l]],d[t]);
        while(l<=r&&cr[q[r]]+dis[i]-dis[q[r]]<=cr[i])
          r--;
        q[++r]=i;
    }//    dp
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        addl(i,x,y);
        addl(x,i,y);
    }
    for (int i=1;i<=n;i++) 
	  if (!v[i]) dfs(i,++t);
    topsort();
    for (int i=1;i<=n;i++){
        if(in[i]>1&&!k[v[i]]) {
            k[v[i]]=1;
            dp(v[i],i);
            ans+=d[v[i]];
        }
    }
    printf("%lld",ans);
}