Yijan's Blog HomeArchives
P4220 [WC2018]通道

Orzwkr

P4220 [WC2018]通道

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

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

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

于是还是考虑根据边分把两边分成两种颜色，然后在第二棵树上建立虚树来 $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)$ 呢？

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#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();
}
文章作者: yijan
文章链接: https://yijan.co/p4220-wc2018tong-dao/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！
边分治线段树合并