Orzwkr

P4220 [WC2018]通道

一眼看上去和 暴力写挂 类似，可是从两棵树变成了三棵树了。

看起来，暴力写挂好像两棵树是极限了，但是这题它满足 $w$ 非负，所以直径是可以合并的。

还是考虑第一棵树上边分，化下式子成为

$$di s(rt,u) + dis(rt,v) + dep_2[u]+dep_2[v]-2dep_2[lca_2(u,v)]+dis_2(a,b)$$

于是还是考虑根据边分把两边分成两种颜色，然后在第二棵树上建立虚树来 $dp$ 。然后考虑怎么维护当前子树内不同颜色的点在第三棵树上的直径长度加上 $dis(rt,u) + dis(rt,v) + dep_2[u] + dep_2[v]$。这个后面的权值我们加虚点挂在第三棵树每个节点的下面，于是变成了一个不同的求不同颜色的点的直径问题。但是直接维护这个不同颜色的直径端点明显是有问题的，我们可以考虑维护出两种颜色分别的点集的直径端点，这样就会很方便合并。这样做的复杂度是 $O(n\log^2n)$ 或者 $O(n\log n)$ 。

能否类似 “暴力写挂” 一题的思路优化到 $O(n\log n)$ 呢？

我们考虑当前式子长成这样：

$$dis(rt,u) + dis(rt,v) + dep_2[u] + dep_2[v] - 2dep[lca( u , v )] + dis_3(u,v)$$

在第一棵树上建立边分树，维护当前边分点两个儿子分别在第三棵树上添加关于当前边分中心所加的虚点后的直径，也就是添加了权值为 $dep_2[u] + dep_2[v] + dis(rt,u) + dis(rt,v)$ 的虚点后的直径。可以发现我们实际上没有必要把虚点给真正添加出来，因为我们求答案的时候是在第二棵树上进行边分树合并，合并的时候只需要判断四对点距离大小关系就好了。而初始化的时候由于只有一个点，是非常好初始化的。。所以我们直接合并边分树就做完了。

然后因为一个符号写反调了好久好久好久好久

暂时是 LOJ rank 4。。（不会卡常）

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 800006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
#define P 998244353
typedef long long ll;

#define inf 0x3f3f3f3f3f3f3f3f
#define lg2( x ) ( 31 - __builtin_clz( x ) )
#define swap( a , b ) ( a ^= b , b ^= a , a ^= b )
int n , N;

ll res = -inf;

inline void rd( int& x ) {
    char ch = ' '; x = 0;
    while( ch > '9' || ch < '0' ) ch = getchar( );
    while( ch >= '0' && ch <= '9' ) x = 10 * x + ch - '0' , ch = getchar();
}
inline void rd( ll& x ) {
    char ch = ' '; x = 0;
    while( ch > '9' || ch < '0' ) ch = getchar( );
    while( ch >= '0' && ch <= '9' ) x = 10 * x + ch - '0' , ch = getchar();
}

int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , ecn = -1;
ll wto[MAXN << 1];
void ade( int u , int v , ll w ) {
//    cout << u << ' ' << v << ' ' << w << endl;
    to[++ ecn] = v , nex[ecn] = head[u] , wto[ecn] = w , head[u] = ecn;
    to[++ ecn] = u , nex[ecn] = head[v] , wto[ecn] = w , head[v] = ecn;
}

/*
 * PreworkS:
 * - First Tree:
 * rebuild
 *
 * - Second Tree:
 * depths
 *
 * - Third Tree:
 * LCA( dis )
 */

vector<pair<int,ll>> G1[MAXN] , G2[MAXN] , G3[MAXN];

void rebuild( int u , int fa ) {
    int last = -1;
    for( auto& t : G1[u] ) if( t.fi != fa ) {
            int v = t.fi;
            if( last == -1 ) ade( u , v , t.se ) , last = u;
            else {
                ++ n;
                ade( last , n , 0 ) , ade( n , v , t.se );
                last = n;
            }
            rebuild( v , u );
        }
}

int bac[MAXN] , dfn[MAXN] , clo; // bac: to seq
ll dep3[MAXN] , dep2[MAXN];
void cfs( int u , int fa ) {
    dfn[++ clo] = u , bac[u] = clo;
    for( auto& t : G3[u] ) if( t.fi != fa ) {
            int v = t.fi;
            dep3[v] = dep3[u] + t.se;
            cfs( v , u );
            dfn[++ clo] = u;
        }
}
void bfs( int u , int fa ) {
    for( auto& t : G2[u] ) if( t.fi != fa ) {
            int v = t.fi;
            dep2[v] = dep2[u] + t.se;
            bfs( v , u );
        }
}

int st[20][MAXN];
void buildST( ) {
    rep( i , 1 , clo ) st[0][i] = dfn[i];
    rep( i , 1 , lg2( clo ) )
        rep( j , 1 , clo - ( 1 << i ) + 1 )
            st[i][j] = ( dep3[st[i - 1][j]] > dep3[st[i - 1][j + ( 1 << i - 1 )]] ? st[i - 1][j + ( 1 << i - 1 )] : st[i - 1][j] );
}
ll dis3( int u , int v ) {
    int l = bac[u] , r = bac[v];
    if( l > r ) swap( l , r );
    int len = lg2( r - l + 1 ) , lca = dep3[st[len][l]] < dep3[st[len][r - ( 1 << len ) + 1]] ? st[len][l] : st[len][r - ( 1 << len ) + 1];
    return dep3[u] + dep3[v] - 2 * dep3[lca];
}

int vis[MAXN] , siz[MAXN] , E , rt , mn;
void getsize( int u , int fa ) {
    siz[u] = 1;
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        getsize( v , u );
        siz[u] += siz[v];
    }
}
void getedge( int u , int fa ) {
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        if( max( siz[v] , siz[rt] - siz[v] ) < mn ) mn = max( siz[v] , siz[rt] - siz[v] ) , E = ( i >> 1 );
        getedge( v , u );
    }
}
inline int getit( int u ) { rt = u , E = -1 , mn = 0x3f3f3f3f; getsize( u , u ) , getedge( u , u ); return E; }


int W;
ll ww;
ll dis[MAXN];

int las[MAXN] , r[MAXN] , ch[MAXN << 3][2] , w[MAXN << 3] , idx;

struct orzwkr {
    ll u , v;
    ll valu , valv;
} dp[MAXN << 3][2] ;

void afs( int u , int fa ) {
    if( u <= N ) {
        if( !las[u] ) r[u] = las[u] = ++idx;
        else ch[las[u]][w[u]] = ++ idx , las[u] = idx;
        w[u] = W;
        dp[idx][W].u = dp[idx][W].v = u;
        dp[idx][W].valu = dp[idx][W].valv = dep2[u] + dis[u];
    }
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        dis[v] = dis[u] + wto[i];
        afs( v , u );
    }
}

void divide( int e ) {
    vis[e] = 1;
    int u = to[e << 1] , v = to[e << 1 | 1];
    dis[u] = 0 , W = 0; afs( u , u );
    dis[v] = wto[e << 1] , W = 1; afs( v , v );
    u = getit( u ) , v = getit( v );
    if( ~u ) divide( u );
    if( ~v ) divide( v );
}

inline ll calc( int u , int v , ll valu , ll valv ) { // u , v , virtual weight valu,valv
    return dis3( u , v ) + ( u != v ? valu + valv : 0 );
}

inline void mergeit( orzwkr& a , const orzwkr& b ) { // merge b to a
    if( !a.u || !b.u ) { a = ( a.u ? a : b ); return; }
    long long cur , t , vu = calc( a.u , a.v , a.valu , a.valv ) , vv = calc( b.u , b.v , b.valu , b.valv );
    orzwkr ret = vu > vv ? a : b;
    cur = max( vu , vv );
    int u , v;
    rep( i , 0 , 1 ) {
        u = ( i ? a.u : a.v ) , vu = ( i ? a.valu : a.valv );
        rep( j , 0 , 1 ) {
            v = ( j ? b.u : b.v ) , vv = ( j ? b.valu : b.valv );
            t = calc( u , v , vu , vv );
            if( t > cur ) ret = (orzwkr) { u , v , vu , vv } , cur = t;
        }
    }
    a = ret;
}

inline ll getit( const orzwkr& a , const orzwkr& b ) { // must choose one from a one from b
    int u , v;
    ll vu , vv;
    ll ans = -inf , t;
    rep( i , 0 , 1 ) {
        u = ( i ? a.u : a.v ) , vu = ( i ? a.valu : a.valv );
        rep( j , 0 , 1 ) {
            v = ( j ? b.u : b.v ) , vv = ( j ? b.valu : b.valv );
            t = calc( u , v , vu , vv );
            if( t > ans ) ans = t;
        }
    }
    return ans;
}

ll ls;
int merge( int u , int v ) { // merge v to u
    if( !u || !v ) return u | v;
    if( dp[u][0].u && dp[v][1].u ) res = max( res , getit( dp[u][0] , dp[v][1] ) + ls );
    if( dp[u][1].u && dp[v][0].u ) res = max( res , getit( dp[u][1] , dp[v][0] ) + ls );
    mergeit( dp[u][0] , dp[v][0] ) , mergeit( dp[u][1] , dp[v][1] );
    ch[u][0] = merge( ch[u][0] , ch[v][0] ) , ch[u][1] = merge( ch[u][1] , ch[v][1] );
    return u;
}

void bfs2( int u , int fa ) {
    for( auto& t : G2[u] ) if( t.fi != fa ) {
            int v = t.fi;
            bfs2( v , u );
            ls = -2 * dep2[u] , merge( r[u] , r[v] );
        }
}

void debug( int u ) {
    if( !u ) return;
    cout << "Now" << ' ' << u << endl;
    cout << dp[u][0].u << ' ' << dp[u][0].v << ' ' << dp[u][0].valu << ' ' << dp[u][0].valv << endl;
    cout << dp[u][1].u << ' ' << dp[u][1].v << ' ' << dp[u][1].valu << ' ' << dp[u][1].valv << endl;
    puts("");
    debug( ch[u][0] ) , debug( ch[u][1] );
}

void solve() {
    cin >> n; N = n;
    rep( i , 1 , n * 2 ) head[i] = -1;
    int u , v; ll w;
    rep( i , 2 , n ) rd( u ) , rd( v ) , rd( w ) , G1[u].eb( mp( v , w ) ) , G1[v].eb( mp( u , w ) );
    rep( i , 2 , n ) rd( u ) , rd( v ) , rd( w ) , G2[u].eb( mp( v , w ) ) , G2[v].eb( mp( u , w ) );
    rep( i , 2 , n ) rd( u ) , rd( v ) , rd( w ) , G3[u].eb( mp( v , w ) ) , G3[v].eb( mp( u , w ) );
    rebuild( 1 , 1 ) , cfs( 1 , 1 ) , bfs( 1 , 1 ) , buildST( );
    divide( getit( 1 ) );
//    debug( r[5] );
    bfs2( 1 , 1 );
    cout << res << endl;
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}