CTSC2018 暴力写挂
题意：
题目传送门
题解：
emm……第一次写边分治…… 考虑到第二棵树上的\(Lca\)我们难以处理，于是我们可以考虑枚举第二棵树上的\(Lca\)，然后在第一棵树上最大化\(dep_u + dep_v - dep_{lca}\)。但是在这个式子中，又受到了第一棵树上\(Lca\)的限制，于是我们考虑化简式子。稍微化简一下会发现式子变成了\(\frac{1}{2} * (dep_u + dep_v + dis_{u, v})\)，然后我们就可以将其转化成无根树来做了。 考虑边分的时候我们应该维护什么东西，我们将\(dis_{u, v}\)拆成\(dis_{u, rt} + dis_{rt, v}\)，其中\(rt\)为当前边分中心的两个点其中的一个点。那么我们就只需要维护\(dis_{x, rt} + dep_x\)的最大值即可。然后我们在第二棵树上枚举\(Lca\)，然后计算贡献即可。最后就是如何合并两个点的贡献，发现我们重建之后的边分树是一棵二叉树，它有着线段树的形态，所以我们直接像线段树合并一样将贡献合并起来即可，复杂度是正确的。
Code
#pragma GCC optimize (2,"inline","Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 500;
typedef pair<int, int> P;
const ll INF = 1e15;
#define fi first
#define se second
#define mk make_pair
struct Graph {
struct edge {
int to, nxt, w;
}E[N << 3];
int head[N << 2];
int tot;
Graph() { tot = 1; memset(head, -1, sizeof head);}
void Addedge(int u, int v, int w) {
E[++tot].to = v; E[tot].nxt = head[u]; head[u] = tot; E[tot].w = w;
E[++tot].to = u; E[tot].nxt = head[v]; head[v] = tot; E[tot].w = w;
}
void Print() {
for(int i = 2; i <= tot; i += 2) {
cerr << E[i].to << " " << E[i ^ 1].to << endl;
}
}
}T1, T2, DvT;
int n, ndcnt, Mn, id, cnt;
int sz[N << 2], vis[N << 3], ch[N << 6][2], rt[N << 2];
P PA[N << 2];
ll val[N << 6][2], dep[N];
ll ans = -INF;
void read(int &x) {
x = 0; int f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f;
}
void Rebuild(int o, int fa) {
int las = o;
for(int i = T1.head[o]; ~i; i = T1.E[i].nxt) {
int to = T1.E[i].to;
if(to == fa) continue;
dep[to] = dep[o] + T1.E[i].w;
Rebuild(to, o);
DvT.Addedge(las, ++ndcnt, 0); DvT.Addedge(ndcnt, to, T1.E[i].w);
las = ndcnt;
}
}
void GetEg(int o, int fa, int SZ) {
sz[o] = 1;
for(int i = DvT.head[o]; ~i; i = DvT.E[i].nxt) {
int to = DvT.E[i].to;
if(to == fa || vis[i]) continue ;
GetEg(to, o, SZ);
sz[o] += sz[to];
if(Mn > max(sz[to], SZ - sz[to])) Mn = max(sz[to], SZ - sz[to]), id = i;
}
}
void Getdep(int o, int fa, ll d, int c) {
if(o <= n) {
++cnt;
if(!PA[o].fi) rt[o] = cnt;
else ch[PA[o].fi][PA[o].se] = cnt;
PA[o] = mk(cnt, c);
val[cnt][c] = dep[o] + d;
val[cnt][c ^ 1] = -INF;
}
sz[o] = 1;
for(int i = DvT.head[o]; ~i; i = DvT.E[i].nxt) {
int to = DvT.E[i].to;
if(to == fa || vis[i]) continue ;
Getdep(to, o, d + DvT.E[i].w, c);
sz[o] += sz[to];
}
}
void Solve(int o, int SZ) {
if(SZ == 1) return ;
Mn = 1e9; GetEg(o, 0, SZ);
int x = DvT.E[id].to, y = DvT.E[id ^ 1].to;
vis[id] = vis[id ^ 1] = 1;
Getdep(x, 0, 0, 0); Getdep(y, 0, DvT.E[id].w, 1);
Solve(x, sz[x]); Solve(y, sz[y]);
}
int Merge(int x, int y, ll Dp) {
if(!x || !y) return x | y;
ans = max(ans, max(val[x][0] + val[y][1], val[x][1] + val[y][0]) - Dp);
val[x][0] = max(val[x][0], val[y][0]); ch[x][0] = Merge(ch[x][0], ch[y][0], Dp);
val[x][1] = max(val[x][1], val[y][1]); ch[x][1] = Merge(ch[x][1], ch[y][1], Dp);
return x;
}
void Dfs(int o, int fa, ll d) {
ans = max(ans, 2ll * (dep[o] - d));
for(int i = T2.head[o]; ~i; i = T2.E[i].nxt) {
int to = T2.E[i].to;
if(to == fa) continue;
Dfs(to, o, d + T2.E[i].w);
rt[o] = Merge(rt[o], rt[to], d * 2);
}
}
int main() {
read(n); ndcnt = n;
for(int i = 1, u, v, w; i < n; i++) {
read(u); read(v); read(w);
T1.Addedge(u, v, w);
}
for(int i = 1, u, v, w; i < n; i++) {
read(u); read(v); read(w);
T2.Addedge(u, v, w);
}
Rebuild(1, 1);
Solve(1, ndcnt);
Dfs(1, 0, 0);
printf("%lld\n", ans / 2);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10569832.html
相关资源：JAVA上百实例源码以及开源项目
