[jzoj5071] [GDSOI 2017 2차 시뮬레이션] [치즈] [나무 동태 기획]

제목의 대의.
CJY가 치즈를 좋아해서 YJC가 치즈를 구했다. 현재 YJC는 CJY와 치즈를 나눠 먹기로 했다.
YJC는 n-1개의 치즈를 구했다. 그래서 그는 n개의 결점이 있는 나무에 치즈를 걸었다. 나뭇가지마다 치즈 한 조각을 달았고 치즈마다 무게가 있었다.
YJC와 CJY는 이렇게 치즈를 나누기로 했다. 먼저 나뭇가지 하나를 잘라내고 나무를 두 부분으로 나누어 각각 일부를 뽑은 다음에 각자 자신이 뽑은 나무에서 경로를 선택하고 경로에 있는 치즈를 가져간 다음에 남은 치즈를 쥐에게 먹였다.
두 사람은 모두 무게가 가장 큰 치즈를 가져가려고 했지만, 어떤 나뭇가지를 잘라내는 것이 가장 좋은지 몰랐다.그래서 나뭇가지 하나하나를 베어낸 치즈의 총 무게의 최대치를 계산해 보라고 한다.
문제풀이의 방향
나무형 동태 기획, 어느 쪽을 매거진 삭제하고 아래 세 개의 체인을 유지하며 위로 한 개의 체인, 자수 직경, 아들 자수 두 개의 직경, 각종if를 유지하면 된다.
code

#include<set>
#include
#include
#include
#include
#define LD double
#define LL long long
#define ULL unsigned long long
#define min(a,b) ((ab)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=4*1e6+9,mm=8*1e6+9,inf=1e9;LL mo=2333333333333333;
int n,gra,tag,ansp,begin[mn],to[mm],len[mm],num[mm],next[mm];
    LL anss,f[mn][4][2],a[mn][3][2],g[mn],h[mn];
void insert(int u,int v ,int w,int p){
    to[++gra]=v;
    len[gra]=w;
    num[gra]=p;
    next[gra]=begin[u];
    begin[u]=gra;
}
void add(int now,int pos,LL far){
    fd(i,3,1){
        if(f[now][i][0]>far)break;
        f[now][i+1][0]=f[now][i][0];
        f[now][i+1][1]=f[now][i][1];
        f[now][i][0]=far;
        f[now][i][1]=pos;
    }
}
void dfs(int now,int pre){
    fr(i,now)if(to[i]!=pre){
        dfs(to[i],now);
        add(now,to[i],f[to[i]][1][0]+len[i]);
        h[now]=max(h[now],h[to[i]]);
    }
    h[now]=max(h[now],f[now][1][0]+f[now][2][0]);
}
LL get(int now,int tag){
    fo(i,1,3)if(f[now][i][1]!=tag)return f[now][i][0];
}
LL get2(int now,int tag){
    if(f[now][1][1]==tag)return f[now][2][0]+f[now][3][0];
    else if(f[now][2][1]==tag)return f[now][1][0]+f[now][3][0];
    else return f[now][1][0]+f[now][2][0];
}
void addh(int now,int pos,LL far){
    fd(i,2,1){
        if(a[now][i][0]>far)break;
        a[now][i+1][0]=a[now][i][0];
        a[now][i+1][1]=a[now][i][1];
        a[now][i][0]=far;
        a[now][i][1]=pos;
    }
}
LL geth(int now,int tag){
    fo(i,1,2)if(a[now][i][1]!=tag)return a[now][i][0];
}
void dfs2(int now,int pre,LL tmx){
    fr(i,now)if(to[i]!=pre)
        addh(now,to[i],h[to[i]]);
    fr(i,now)if(to[i]!=pre){
        LL tmp=get(now,to[i]);
        g[to[i]]=max(tmp,g[now])+len[i];
        tmp=h[to[i]];LL tmp2=get2(now,to[i]),tmp3=get(now,to[i])+g[now];
        tmp2=max(tmp2,tmp3);tmp3=geth(now,to[i]);
        tmp2=max(tmp2,tmp3);
        tmp2=max(tmp2,tmx);
        tmp3=max(tmp,tmp2);LL tmp4=min(tmp,tmp2);
        anss=(anss+tmp3*23333+tmp4*2333+1ll*233*num[i]*num[i]+23*num[i]+2)%mo;
        dfs2(to[i],now,tmp2);
    }
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d",&n);int u,v,w;
    fo(i,1,n-1){
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w,i);insert(v,u,w,i);
    }
    dfs(1,0);
    dfs2(1,0,0);
    printf("%lld",anss);
    return 0;
}