当前位置 博文首页 > ApocalypseTq的博客：P4565 [CTSC2018]暴力写挂 题解
感谢i207M神犇教我的边分树Orz
这题让我们求这个：
ans=max_{x,y}\{deep_x+deep_y-deep_{LCA(x,y)}-deep'_{LCA'(x,y)}\}ans=maxx,y?{deepx?+deepy??deepLCA(x,y)??deepLCA′(x,y)′?}
然后这式子里带了2个LCA不好处理，给他变形：
ans=\frac 1 2max_{x,y}\{dis(x,y)+deep_x+deep_y-2deep'_{LCA'(x,y)}\}ans=21?maxx,y?{dis(x,y)+deepx?+deepy??2deepLCA′(x,y)′?}
然后这里出现了dis(x,y)dis(x,y)，不难想到通道那题的边分治做法，我们把它照搬过来，对T_1T1?进行边分治，然后这个过程中划分了两个连通块，把一边的看成黑点，一边的看成白点，然后令val_ivali?为当前边分治的时候的ii的深度+deep_i+deepi?，那么我们相当于最大化val_x+val_y-2deep'_{LCA'(x,y)}valx?+valy??2deepLCA′(x,y)′?，其中x为黑点，y为白点，这个在T_2T2?上建个虚树枚举LCA'LCA′就可以统计答案了，加上建虚树的排序这是O(n\log^2n)O(nlog2n)的显然同一位出题人故意卡了这个过不去……毕竟1个log都要跑2s多……
然后我们把上面那个思路稍微改一下，考虑在T_2T2?上直接枚举LCA'LCA′，然后合并两棵LCA'LCA′为这个点的子树的时候统计这两棵子树之间在T_1T1?上产生的贡献，然而显然我们就不能边分治了，然而……有个东西叫边分树……
所谓边分树其实和点分树完全不同，实际上它初始的时候是一个森林的形式，我们先对T_1T1?进行一遍边分治，然后我们在每个点上维护一条高度为O(logn)的二叉树链O(logn)的二叉树链（注意此树非彼树），在分治的时候，我们把一端深度较大的那个连通块里的所有点的链的底部都添加一个右儿子，深度较小的那一端的连通块的所有点都添加一个左儿子。这里所说的“深度”是用于区分这条边的两个端点的。每个点上维护的这条链上的点其实就是表示了这个点自己在边分治时所属的O(\log n)O(logn)个连通块。所以这个空间复杂度是O(\log n)O(logn)的，其实这个类似于动态开点线段树。
然后考虑两个T_1T1?上的点aa和bb什么时候会产生贡献，显然就是两个点第一次不在一个连通块内，也就是说，考虑a的边分树上一个点ii与b的边分树上一个点j，ijij深度相同，那么i的所有祖先的左右父子关系都与j的相同，直到i和j他们与父亲的左右父子关系才开始变得不同。
那么，我们就可以对边分树进行合并了，这个合并和线段树合并完全一样，同时我们可以在合并的时候顺便把对答案的贡献统计出来。我们现在不是在枚举LCA'LCA′吗？就在这个dfsdfs的时候合并子树的边分树，我们求的相当于最大的val_i+val_jvali?+valj?，当合并abab两棵边分树的时候，显然aa的所有祖先的父子的左右关系都和bb的相等（因为这个和线段树合并一样），那么就相当于abab表示的是同一个连通块，我们就可以把他们合并成一个点，同时维护这个点表示的连通块里最大的valval（取个max即可），然后a的左儿子显然是和b的右儿子分治在一条边的两边的，同理a的右儿子与b的左儿子也如此，那么把他们产生的贡献统计一下即可。于是就做到了O(n\log n)O(nlogn)。
不难发现，我们最后会合并成一棵极大的边分树，这棵边分树就真的是真正意义上的“边分树”了，即父亲的左右儿子是一个大连通块分治成的两个小连通块，另外还要注意在边分树上维护子树的信息没有任何意义……
哦这题还需要特判x=yx=y的情况，因为你的答案是边分树合并统计出来的，所以一个点自身与自身的答案统计不出来……
上代码~
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
#define inf (1ll << 60)
#define abs(_o) ((_o < 0) ? -(_o) : _o)
using namespace std;
namespace ywy {
inline int get() {
int n = 0;
char c;
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
break;
if (c == '-')
goto s;
}
n = c - '0';
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
n = n * 10 + c - '0';
else
return (n);
}
s:
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
n = n * 10 - c + '0';
else
return (n);
}
}
int n;
typedef struct _b {
int dest;
int nxt;
int len;
unsigned char gg;
} bian;
int root[400001];
ll val[10000001];
int gb;
int ch[10000001][2];
namespace t1 {
bian memchi[2000001];
int gn = 2, heads[800001];
inline void add(int s, int t, int l) {
memchi[gn].dest = t;
memchi[gn].len = l;
memchi[gn].nxt = heads[s];
heads[s] = gn;
gn++;
}
ll deep[800001];
int size[800001], tot, zx, minn;
ll dp[800001];
int rdp[800001];
void dfs(int pt, int baba) {
for (register int i = heads[pt]; i; i = memchi[i].nxt) {
if (memchi[i].dest == baba)
continue;
deep[memchi[i].dest] = deep[pt] + memchi[i].len;
rdp[memchi[i].dest] = rdp[pt] + 1;
dfs(memchi[i].dest, pt);
}
}
void afs(int pt, int baba) {
tot++;
for (register int i = heads[pt]; i; i = memchi[i].nxt) {
if (memchi[i].gg || memchi[i].dest == baba)
continue;
afs(memchi[i].dest, pt);
}
}
void bfs(int pt, int baba) {
size[pt] = 1;
for (register int i = heads[pt]; i; i = memchi[i].nxt) {
if (memchi[i].gg || memchi[i].dest == baba)
continue;
bfs(memchi[i].dest, pt);
size[pt] += size[memchi[i].dest];
if (abs(tot - 2 * size[memchi[i].dest]) < minn) {
minn = abs(tot - 2 * size[memchi[i].dest]);
zx = i;
}
}
}
void cfs(int pt, int baba, int op) {
if (pt <= n) {
int me = gb;
gb++;
val[me] = deep[pt] + dp[pt];
ch[root[pt]][op] = me;
root[pt] = me;
}
for (register int i = heads[pt]; i; i = memchi[i].nxt) {
if (memchi[i].dest == baba || memchi[i].gg)
continue;
dp[memchi[i].dest] = dp[pt] + memchi[i].len;
cfs(memchi[i].dest, pt, op);
}
}
void digui(int pt) {
tot = 0;
afs(pt, 0);
if (tot == 1)
return;
minn = 12345678;
bfs(pt, 0);
int me = zx, a = memchi[me].dest, b = memchi[me ^ 1].dest;
memchi[me].gg = memchi[me ^ 1].gg = 1;
dp[a] = memchi[me].len;
dp[b] = 0;
cfs(a, 0, rdp[a] > rdp[b]);
cfs(b, 0, rdp[b] > rdp[a]);
digui(a);
digui(b);
}
}
vector<int> vec[400001], len[400001];
int gpt;
void rebuild(int pt, int baba) {
int lst = pt;
for (register int i = 0; i < vec[pt].size(); i++) {
if (vec[pt][i] == baba)
continue;
int me = gpt;
gpt++;
t1::add(lst, me, 0);
t1::add(me, lst, 0);
t1::add(me, vec[pt][i], len[pt][i]);
t1::add(vec[pt][i], me, len[pt][i]);
rebuild(vec[pt][i], pt);
lst = me;
}
}
ll maxn = -inf;
ll ans = -inf;
inline int united(int a, int b) {
if (!(a && b))
return (a | b);
if (ch[a][0] && ch[b][1]) {
ans = max(ans, val[ch[a][0]] + val[ch[b][1]]);
}
if (ch[a][1] && ch[b][0]) {
ans = max(ans, val[ch[a][1]] + val[ch[b][0]]);
}
val[a] = max(val[a], val[b]);
ch[a][0] = united(ch[a][0], ch[b][0]);
ch[a][1] = united(ch[a][1], ch[b][1]);
return (a);
}
namespace t2 {
bian memchi[1000001];
int gn = 1, heads[400001];
inline void add(int s, int t, int l) {
memchi[gn].dest = t;
memchi[gn].len = l;
memchi[gn].nxt = heads[s];
heads[s] = gn;
gn++;
}
ll deep[400001];
void dfs(int pt, int baba) {
for (register int i = heads[pt]; i; i = memchi[i].nxt) {
if (memchi[i].dest == baba)
continue;
deep[memchi[i].dest] = deep[pt] + memchi[i].len;
dfs(memchi[i].dest, pt);
ans = -inf;
root[pt] = united(root[pt], root[memchi[i].dest]);
if (ans != -inf)
maxn = max(maxn, ans - 2 * deep[pt]);
}
}
}
void ywymain() {
n = get();
gpt = n + 1;
for (register int i = 1; i <= n; i++) root[i] = i;
gb = n + 1;
val[0] = -inf;
for (register int i = 1; i < n; i++) {
int s = get(), t = get(), l = get();
vec[s].push_back(t);
len[s].push_back(l);
vec[t].push_back(s);
len[t].push_back(l);
}
for (register int i = 1; i < n; i++) {
int s = get(), t = get(), l = get();
t2::add(s, t, l);
t2::add(t, s, l);
}
rebuild(1, 0);
t1::dfs(1, 0);
t1::digui(1);
for (register int i = 1; i <= n; i++) root[i] = i;
t2::dfs(1, 0);
maxn /= 2;
for (register int i = 1; i <= n; i++) {
maxn = max(maxn, t1::deep[i] - t2::deep[i]);
}
cout << maxn << endl;
}
}
int main() {
ywy::ywymain();
return (0);
}