[LA 4454] Subway Timing

作法：

首先考慮二分搜答案，這樣變成對於一個給定的誤差$M$，是否有辦法把邊權都改成$60$的倍數，使得任兩點之間的距離誤差絕對值不會超過$M$。對於一個子樹來說，記他的根為$R$，假設有一種改邊權的方法，使得這棵子樹中任兩點之間的距離誤差絕對值不會超過$M$，並且$R$到這棵子樹中每個點的距離誤差最小值為$a$，最大值為$b$（這裡的誤差指的是「新的距離扣掉舊的距離」的值，有正有負，因此這裡顯然會有$a\leq 0,b\geq 0$），那麼這個設邊權的方法就只有$a,b$是跟之後決策有關的資訊了。也就是一個節點需要的 dp 值會是一大堆的$(a,b)$ 的 pair 。實際上我們可以不用把所有的$(a,b)$都紀錄起來，觀察到如果有兩個 pair $(a_1,b_1),(a_2,b_2)$，滿足$a_2\leq a_1$且$b_2\geq b_1$，那麼取$(a_1,b_1)$一定會比取$a_2,b_2$好，因此我們可以只維護$a$值和$b$值都嚴格遞增的 pair 們就可以了。

轉移比較麻煩，我們可以把題目轉成二元樹比較好DP。轉成二元樹的方法如下圖（對每個節點都做這種轉換即可），其中紅色的點是新加的點，左右圖中的藍色的邊的邊權是相等的，並且紅色邊的邊權為$0$。

轉成二元樹之後工作就只剩下合併兩個子節點的 dp 陣列了，假設當前節點為$x$，並且我們已經決定好$x$連向他兩個子樹的邊的新邊權了，記這兩條邊的誤差分別為$dx,dy$（也就是新邊權扣掉舊邊權的值），那麼考慮左子樹 DP 陣列中的某個$(a_1,b_1)$，還有右子樹中的某個$(a_2,b_2)$，這兩個 pair 分別都代表了他所在子樹的某個設置邊權的方法。接下來我們想知道把這兩個方法並在一起是不是可行的，並且如果可以的話要知道$x$的 DP 陣列必須多丟什麼 pair 進去。我們想要知道這兩個 pair 是否是可行的，而可行的充要條件就是任兩點距離的誤差絕對值$\leq M$。分成$x$到非根節點和左子樹中的點到右子樹中的點來討論，考慮前者則必須滿足：$|a_1+dx|\leq M,|b_1+dx|\leq M,|a_2+dy|\leq M,|b_2+dy|\leq M$。後者的話則必須滿足：$|a_1+a_2+dx+dy|\leq M,|b_1+b_2+dx+dy|\leq M$。並且如果$(a_1,b_1),(a_2,b_2)$都滿足前面那些條件的話，那麼$dp[x]$就會新增一個 pair ：$(min(a_1+dx,a_2+dy,0),max(b_1+dx,b_2+dy,0))$。

我們當然不能枚舉所有左右子樹形成的 pair 的二元組，注意到當我們固定$(a_1,b_1)$時，我們可以把上述條件全部整理成：$a_2\leq $一坨東西、$a_2\geq $一坨東西（$b_2$）亦同，這裡就可以利用這些 pair 的遞增性，可以得到第二個子樹中滿足那些條件的 pair 會落在某個區間中（如果我們已經把子樹中的 pair 們排好序了），而我們不難用二分搜找出這個區間。再觀察到新增的 pair 的式子，可以不妨設$a_1+dx\leq a_2+dy$，因為我們可以把兩個子樹交換再作一次，因此新增的 pair 的第一項的值已經確定了，並且我們知道此時第二項要越小越好，也就是 $b_2$ 越小越好，因此我們只要枚舉第一個子樹中的$(a_1,b_1)$，並且取剛剛找到的那個區間的第一個 pair 就可以了，拿他配上$(a_1,b_1)$去更新$dp[x]$即可（當然當這個區間不存在時就沒辦法更新）。

code :

#include<bits/stdc++.h>
#define MIN(X,Y,Z) min(min(X,Y),Z)
#define MAX(X,Y,Z) max(max(X,Y),Z)
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=400+10 ;
 
struct P{int to,dis;};
vector<P> v[maxn] ;
void dfs0(int x,int f)
{
    for(int i=0;i<v[x].size();i++)
    {
        if(v[x][i].to==f)
        {
            swap(v[x][i],v[x].back()) ;
            v[x].pop_back() ;
            i-- ;
        }
        else dfs0(v[x][i].to,x) ;
    }
}
 
int n,n2 ;
void get_binary()
{
    n2=n ; dfs0(1,1) ;
    for(int i=1;i<=n;i++) if(v[i].size()>2)
    {
        int sz=v[i].size() ;
        for(int j=1;j<sz-2;j++)
            v[n2+j].push_back(v[i][j]) ,
            v[n2+j].push_back((P){n2+j+1,0}) ;
        v[n2+sz-2].push_back(v[i][sz-2]) ;
        v[n2+sz-2].push_back(v[i][sz-1]) ;
        v[i][1]=(P){n2+1,0} ; v[i].resize(2) ;
        n2+=sz-2 ;
    }
}
 
int lb1(const vector<pii> &p,int x)
{
    return lower_bound(p.begin(),p.end(),pii(x,-1e9))-p.begin() ;
}
int lb2(const vector<pii> &p,int x)
{
    int l=-1 , r=p.size() ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(p[mid].S>=x) r=mid ;
        else l=mid ;
    }
    return r ;
}
 
bool cmp(const pii &a,const pii &b)
{
    return a.F!=b.F ? a.F<b.F : a.S>b.S ;
}
void normalize(vector<pii> &vp)
{
    sort(vp.begin(),vp.end(),cmp) ;
    int sz2=0 ;
    for(int i=0;i<vp.size();i++)
    {
        while(sz2 && vp[i].S<=vp[sz2-1].S) sz2-- ;
        vp[sz2++]=vp[i] ;
    }
    vp.resize(sz2) ;
}
 
void process(int dx,int dy,const pii &p,const vector<pii> &vp,vector<pii> &r,int M)
{
    int a1=p.F , b1=p.S ;
    if(a1+dx<-M || a1+dx>M || b1+dx<-M || b1+dx>M) return ;
    int id=max(lb1(vp,MAX(-M-dx-dy-a1,dx-dy+a1,-M-dy)),
               lb2(vp,max(-M-dx-dy-b1,-M-dy))) ;
    if(id==vp.size()) return ;
    int a2=vp[id].F , b2=vp[id].S ;
    if(a2<=min(M-dy,M-dx-dy-a1) && b2<=min(M-dx-dy-b1,M-dy))
        r.push_back(pii(MIN(a1+dx,a2+dy,0),MAX(b1+dx,b2+dy,0))) ;
}
 
vector<pii> dp[maxn] ;
bool vis[maxn] ;
bool DP(int x,int M,int f=-1)
{
    vis[x]=1 ;
    dp[x].clear() ;
    if(v[x].empty())
    {
        dp[x].push_back((pii){0,0}) ;
        return 1 ;
    }
    for(auto i : v[x]) if(!DP(i.to,M,x)) return 0 ;
    if(v[x].size()==1)
    {
        P &son=v[x][0] ;
        for(int i=son.dis/60*60,t=0;t<2;t++,i+=60)
        {
            int dx=i-son.dis ;
            for(auto it : dp[son.to])
                if(it.F+dx>=-M && it.F+dx<=M && it.S+dx>=-M && it.S+dx<=M)
                dp[x].push_back(pii(min(0,it.F+dx),max(0,it.S+dx))) ;
        }
        normalize(dp[x]) ;
        return !dp[x].empty() ;
    }
 
    for(int i=v[x][0].dis/60*60,t1=0;t1<2;t1++,i+=60)
        for(int j=v[x][1].dis/60*60,t2=0;t2<2;t2++,j+=60)
    {
        int dx=i-v[x][0].dis , dy=j-v[x][1].dis ;
        for(auto it : dp[v[x][0].to]) process(dx,dy,it,dp[v[x][1].to],dp[x],M) ;
        for(auto it : dp[v[x][1].to]) process(dy,dx,it,dp[v[x][0].to],dp[x],M) ;
    }
    normalize(dp[x]) ;
    return !dp[x].empty()  ;
}
 
bool check(int M)
{
    return DP(1,M) ;
}
 
void solve(int tc)
{
    for(int i=0;i<=2*n;i++) v[i].clear() , dp[i].clear() ;
    for(int i=1;i<n;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
    get_binary() ;
 
    int l=-1 , r=60*n ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    printf("Case %d: %d\n",tc,r) ;
}
 
main()
{
    int tc=0 ;
    while(scanf("%d",&n)==1 && n) solve(++tc) ;
}