P4565 [CTSC2018]暴力写挂

真 · 边分治从入门到入土。。

P4565 [CTSC2018]暴力写挂

神仙题。。

我们考虑化一下式子，同时设 $dep[x]$ 为第一棵树的深度，$dep_2[x]$ 为第二棵树的深度，$dis(x,y)$ 为两个点在第一棵树的距离，于是去掉第一棵树上的 LCA :

$f(x,y) = \frac 1 2 (dep[x] + dep[y] + dis(x,y)+dep_2[LCA_2(x,y)])$

由于深度这个东西显然可以三度化来做的，考虑在第一棵树上边分治，对每个点维护 $dep[x] + dis(rt,x)$ 。然后考虑在第二个树里面把这次边分的点拿出来建立一个虚树，这个虚树上我们需要算的是不同子树间的最大的两类点之间的权值和 + LCA 处的深度的最大值。这个可以通过一个简单的树形 dp 来解决。

我们考虑这个过程，边分治带一个 $\log$ ，建立虚树需要排序又是一个 $\log$ ，两个 $\log$ 显然不足以通过本题。我们考虑一个优化，建立虚树的时候的 LCA 是可以 $O(1)$ 的，但是能不能不排序呢？我们可以开头就对所有点按照 dfn 进行排序，每次分治的时候按照 dfn 顺序把当前分治中心的所有点下放到下一次的两块。这样就可以优化建虚树的过程了。复杂度是 $O(n\log n)$ 。

结束了吗？

并没有。还有一个更加优秀的做法。

我们考虑建立出边分树。明显，边分树是一个二叉树。建立方法就是在每次边分的时候新建一个点，左儿子子树中是一边的节点，右儿子是另一边。我们在边分树上的每一个节点，只需要维护这个节点左/右儿子中的最大的权值（ $dp[x]+dis(rt,x)$ ）。然后我们查的最大值就是这个点的 $val[u][0] + val[u][1] + len$ 其中 $len$ 为这个边的长度。

于是考虑，点分树其实是可以动态维护的。具体来说，当我们把这个形态建立出来后，可以考虑一个一个点插入到点分树中，插入的过程中会影响其祖先的 $val[u][0/1]$ 。并且我们知道边分树只有 $\log$ 层，所以每次插入可以直接对每层祖先更新一下 $val$。

可以发现这个东西和线段树其实长的很像的。所以我们可以在第二棵树上，每个点最开始都自成一棵点分树，上面只插入了这个点本身，然后进行线段树合并就好了。合并的过程中同样更新 $val$ 并且算进这个点的答案就好。

复杂度证明类似线段树合并复杂度证明，总复杂度 $O(n\log n)$

为了实现方便，我们可以钦定算右儿子的时候是加上了路径长度的。

（我觉得可能要码很久（而且做完没睡够现在脑子很糊））

开始暴力特判写挂挂了两个点。

#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;
int n , m , p , N;

#define inf 0x3f3f3f3f3f3f3f3f

vector<pii> G1[MAXN] , G2[MAXN];
int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wto[MAXN << 1] , ecn = -1;
void ade( int u , int v , int w ) {
    to[++ ecn] = v , nex[ecn] = head[u] , head[u] = ecn , wto[ecn] = w;
    to[++ ecn] = u , nex[ecn] = head[v] , head[v] = ecn , wto[ecn] = w;
}

long long dep[MAXN];
void rebuild( int u , int fa ) {
    int cur = 0 , last = 0;
    for( pii& t : G1[u] ) {
        int v = t.fi;
        if( v == fa ) continue;
        if( !last ) { last = u; ade( u , v , t.se ); }
        else {
            cur = ++ n;
            ade( last , cur , 0 ) , ade( cur , t.fi , t.se );
            last = cur;
        }
        dep[v] = dep[u] + t.se;
        rebuild( v , u );
    }
}

int vis[MAXN] , siz[MAXN] , rt , E; long long 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 );
    }
}
int getit( int u ) {
    rt = u , mn = inf , E = -1; getsize( u , u ); getedge( u , u ); return E;
}

int last[MAXN] , r[MAXN] , ch[MAXN * 10][2] , idx;
long long dis[MAXN] , val[MAXN * 10][2];
vi pts;

int w[MAXN] , W;
void dfs( int u , int fa ) {
    if( u <= N ) {
        if( last[u] ) ch[last[u]][w[u]] = ++ idx , last[u] = idx;
        else r[u] = last[u] = ++ idx;
        w[u] = W , val[last[u]][W] = dis[u] + dep[u] , val[last[u]][W ^ 1] = -inf;
    }

    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];
        dfs( v , u );
    }
}

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

long long ans = -inf , ls;
int merge( int u , int v ) {
    if( !u || !v ) return u | v;
    ans = max( ans , max( val[u][0] + val[v][1] , val[u][1] + val[v][0] ) + ls );
    val[u][0] = max( val[u][0] , val[v][0] ) , val[u][1] = max( val[u][1] , val[v][1] );
    ch[u][0] = merge( ch[u][0] , ch[v][0] ) , ch[u][1] = merge( ch[u][1] , ch[v][1] );
    return u;
}

long long dep2[MAXN];

void Just_DOIT( int u , int fa ) {
    ans = max( ans , dep[u] * 2 - dep2[u] * 2 );
    for( pii& t : G2[u] ) if( t.fi != fa ) {
        int v = t.fi;
        dep2[v] = dep2[u] + t.se;
        Just_DOIT( v , u );
        ls = - 2 * dep2[u] , r[u] = merge( r[u] , r[v] );
    }
}

void solve() {
    memset( head , -1 , sizeof head );
    cin >> n; N = n;
    int u , v , w;
    rep( i , 2 , n ) scanf("%d%d%d",&u,&v,&w) , G1[u].eb( mp( v , w ) ) , G1[v].eb( mp( u , w ) );
    rep( i , 2 , n ) scanf("%d%d%d",&u,&v,&w) , G2[u].eb( mp( v , w ) ) , G2[v].eb( mp( u , w ) );
    rebuild( 1 , 1 );
    divide( getit( 1 ) );
    Just_DOIT( 1 , 1 );
    cout << ( ans >> 1 ) << endl;
}

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