【BZOJ 5152】【UOJ 347】【WC 2018】通路
8933 ワード
【タイトルリンク】 BZOJ UOJ
【考え方のポイント】まず、2本の木しかない場合を考えてみましょう. 最初のツリー上の2つの点のLCAを列挙すると、この2つの点はLCAの異なるサブツリーに位置するべきであり、点対((x,y))の価値は(deptha_x+deptha_y-2*deptha_{Lca}+distb(x,y))であるべきである. は、2本目のツリー上の各点(x)について、新規(x')が接続され、エッジ重みが(deptha_x)である.この場合、(distb(x',y')=(deptha_x+deptha_y)*[x'ey']+distb(x,y))があり、上記の式と組み合わせて、我々の目標は最も大きい(distb(x',y'))であり、ここで(x)と(y)は(Lca)に属する異なるサブツリーであることが分かった. エッジ重みが負でない図では、集合(A)、(B)にまたがる最長チェーンの端点は、必ず(A)の最長チェーンの端点と(B)の最長チェーンの端点のいずれかであってもよいという性質がある.この結論は,木の直径を証明するような方法で証明できる. したがって,1本目の木に木DPを行い,現在の集合の中で最も長い鎖の2つの端点を維持し,マージ時に答えを更新すればよい. さらに3本の木を考えて、私たちは3本目の木を改造して、それを2叉の木に改造して、そしてそれを辺分治します. 現在の分治集合における1本目の木に対応する点について虚樹を構築し、2本目の木にある各点(x)、新規(x')を接続し、辺権は(deptha_x+distc_x)であり、ここで(distc_x)は点(x)が3本目の木において分治重心までの距離を表す. それから2本の木をセットすればいいです. 時間複雑度(O(Nlog^2 N)).
【コード】
【考え方のポイント】
【コード】
#include
using namespace std;
const int MAXN = 200005;
const int MAXLOG = 19;
template void chkmax(T &x, T y) {x = x > y ? x : y; }
template void chkmin(T &x, T y) {x = min(x, y); }
template void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template void writeln(T x) {
write(x);
puts("");
}
struct edge {int dest; long long len; };
struct info {int x, y; long long len; };
vector a[MAXN], b[MAXN], c[MAXN];
vector e[MAXN];
int n, csize;
int timer, dfn[MAXN];
long long distc[MAXN], ans; info d[2][MAXN];
int fa[MAXN][MAXLOG], deptha[MAXN]; long long dista[MAXN];
int fb[MAXN][MAXLOG], depthb[MAXN]; long long distb[MAXN];
int lca(int x, int y) {
if (deptha[x] < deptha[y]) swap(x, y);
for (int i = MAXLOG - 1; i >= 0; i--)
if (deptha[fa[x][i]] >= deptha[y]) x = fa[x][i];
if (x == y) return x;
for (int i = MAXLOG - 1; i >= 0; i--)
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
int lcb(int x, int y) {
if (depthb[x] < depthb[y]) swap(x, y);
for (int i = MAXLOG - 1; i >= 0; i--)
if (depthb[fb[x][i]] >= depthb[y]) x = fb[x][i];
if (x == y) return x;
for (int i = MAXLOG - 1; i >= 0; i--)
if (fb[x][i] != fb[y][i]) {
x = fb[x][i];
y = fb[y][i];
}
return fb[x][0];
}
long long calca(int x, int y) {
return dista[x] + dista[y] - 2 * dista[lca(x, y)];
}
long long calcb(int x, int y) {
return distb[x] + distb[y] - 2 * distb[lcb(x, y)];
}
long long calc(int x, int y) {
return calcb(x, y) + distc[x] + distc[y];
}
void merge(info &a, info b) {
if (a.len == -1) {
a = b;
return;
}
if (b.len == -1) return;
long long tmp[6], Max = -1e18;
tmp[0] = calc(a.x, b.x), chkmax(Max, tmp[0]);
if (b.x != b.y) tmp[1] = calc(a.x, b.y), chkmax(Max, tmp[1]);
else tmp[1] = 0;
if (a.y != a.x) tmp[2] = calc(a.y, b.x), chkmax(Max, tmp[2]);
else tmp[2] = 0;
if (b.x != b.y) tmp[3] = calc(a.y, b.y), chkmax(Max, tmp[3]);
else tmp[3] = 0;
tmp[4] = a.len; chkmax(Max, tmp[4]);
tmp[5] = b.len; chkmax(Max, tmp[5]);
a.len = Max;
if (tmp[0] == Max) a.x = a.x, a.y = b.x;
else if (tmp[1] == Max) a.x = a.x, a.y = b.y;
else if (tmp[2] == Max) a.x = a.y, a.y = b.x;
else if (tmp[3] == Max) a.x = a.y, a.y = b.y;
else if (tmp[4] == Max) a.x = a.x, a.y = a.y;
else if (tmp[5] == Max) a.x = b.y, a.y = b.x;
}
void update(info a, info b, long long mns) {
if (a.len == -1) return;
if (b.len == -1) return;
chkmax(ans, calc(a.x, b.x) - mns);
chkmax(ans, calc(a.x, b.y) - mns);
chkmax(ans, calc(a.y, b.x) - mns);
chkmax(ans, calc(a.y, b.y) - mns);
}
void dfsa(int pos, int f) {
fa[pos][0] = f;
deptha[pos] = deptha[f] + 1;
dfn[pos] = ++timer;
for (int i = 1; i < MAXLOG; i++)
fa[pos][i] = fa[fa[pos][i - 1]][i - 1];
for (unsigned i = 0; i < a[pos].size(); i++)
if (a[pos][i].dest != f) {
dista[a[pos][i].dest] = dista[pos] + a[pos][i].len;
dfsa(a[pos][i].dest, pos);
}
}
void dfsb(int pos, int f) {
fb[pos][0] = f;
depthb[pos] = depthb[f] + 1;
for (int i = 1; i < MAXLOG; i++)
fb[pos][i] = fb[fb[pos][i - 1]][i - 1];
for (unsigned i = 0; i < b[pos].size(); i++)
if (b[pos][i].dest != f) {
distb[b[pos][i].dest] = distb[pos] + b[pos][i].len;
dfsb(b[pos][i].dest, pos);
}
}
void rebuild(int pos, int fa) {
for (unsigned i = 0; i < c[pos].size(); i++)
if (c[pos][i].dest == fa) swap(c[pos][i], c[pos][0]);
while (c[pos].size() > 3) {
int size = c[pos].size();
int x = c[pos][size - 1].dest;
int y = c[pos][size - 2].dest;
c[pos].resize(size - 2); csize++;
c[csize].push_back((edge) {pos, 0});
c[csize].push_back((edge) {x, c[pos][size - 1].len});
c[csize].push_back((edge) {y, c[pos][size - 2].len});
c[pos].push_back((edge) {csize, 0});
for (unsigned i = 0; i < c[x].size(); i++)
if (c[x][i].dest == pos) c[x][i].dest = csize;
for (unsigned i = 0; i < c[y].size(); i++)
if (c[y][i].dest == pos) c[y][i].dest = csize;
}
for (unsigned i = 0; i < c[pos].size(); i++)
if (c[pos][i].dest != fa) rebuild(c[pos][i].dest, pos);
}
int cnt, s[MAXN];
int col[MAXN], size[MAXN], type[MAXN];
int pointx, pointy, weight, ccnt; long long flen;
void work(int pos, int fa, long long add) {
d[0][pos] = (info) {-1, -1, -1};
d[1][pos] = (info) {-1, -1, -1};
if (type[pos]) {
if (type[pos] == 1) d[0][pos] = (info) {pos, pos, 0};
else d[1][pos] = (info) {pos, pos, 0};
distc[pos] += dista[pos];
}
for (unsigned i = 0; i < e[pos].size(); i++)
if (e[pos][i] != fa) {
work(e[pos][i], pos, add);
update(d[0][pos], d[1][e[pos][i]], 2 * dista[pos] - add);
update(d[1][pos], d[0][e[pos][i]], 2 * dista[pos] - add);
merge(d[0][pos], d[0][e[pos][i]]);
merge(d[1][pos], d[1][e[pos][i]]);
}
}
void calroot(int pos, int colour, int fa, long long len, int tot) {
size[pos] = 1;
for (unsigned i = 0; i < c[pos].size(); i++)
if (c[pos][i].dest != fa && col[c[pos][i].dest] == colour) {
calroot(c[pos][i].dest, colour, pos, c[pos][i].len, tot);
size[pos] += size[c[pos][i].dest];
}
int tmp = max(size[pos], tot - size[pos]);
if (tmp < weight) {
flen = len;
weight = tmp;
pointx = pos;
pointy = fa;
}
}
void calsize(int pos, int colour, int fa, int t) {
size[pos] = 1;
type[pos] = t;
col[pos] = ccnt;
if (pos <= n) s[++cnt] = pos;
for (unsigned i = 0; i < c[pos].size(); i++)
if (c[pos][i].dest != fa && col[c[pos][i].dest] == colour) {
distc[c[pos][i].dest] = distc[pos] + c[pos][i].len;
calsize(c[pos][i].dest, colour, pos, t);
size[pos] += size[c[pos][i].dest];
}
}
bool cmp(int x, int y) {
return dfn[x] < dfn[y];
}
void addedge(int x, int y) {
e[x].push_back(y);
e[y].push_back(x);
}
void maketree(long long add) {
s[++cnt] = 1;
for (int i = 1; i <= cnt - 1; i++)
if (s[i] == 1) {
cnt--;
break;
}
sort(s + 1, s + cnt + 1, cmp);
static int Stack[MAXN]; int top = 0;
Stack[++top] = 1; e[1].clear();
for (int i = 2; i <= cnt; i++) {
int Lca = lca(s[i], Stack[top]);
if (Lca == Stack[top]) {
e[s[i]].clear();
Stack[++top] = s[i];
continue;
}
while (dfn[Lca] <= dfn[Stack[top - 1]]) {
int x = Stack[top--];
int y = Stack[top];
addedge(x, y);
}
if (Lca == Stack[top]) {
e[s[i]].clear();
Stack[++top] = s[i];
} else {
e[Lca].clear();
addedge(Lca, Stack[top]);
Stack[top] = Lca;
e[s[i]].clear();
Stack[++top] = s[i];
}
}
while (top >= 2) {
int x = Stack[top--];
int y = Stack[top];
addedge(x, y);
}
work(1, 0, add);
}
void divide(int pos, int colour, int tot) {
if (tot == 1) return;
weight = tot;
calroot(pos, colour, 0, 0, tot);
int tmpx = pointx, tmpy = pointy;
ccnt++; distc[tmpx] = 0; calsize(tmpx, colour, tmpy, 1);
ccnt++; distc[tmpy] = 0; calsize(tmpy, colour, tmpx, 2);
maketree(flen);
for (int i = 1; i <= cnt; i++)
type[s[i]] = 0;
cnt = 0;
divide(tmpx, col[tmpx], size[tmpx]);
divide(tmpy, col[tmpy], size[tmpy]);
}
int main() {
read(n);
for (int i = 1; i <= n - 1; i++) {
int x, y; long long z;
read(x), read(y), read(z);
a[x].push_back((edge) {y, z});
a[y].push_back((edge) {x, z});
}
for (int i = 1; i <= n - 1; i++) {
int x, y; long long z;
read(x), read(y), read(z);
b[x].push_back((edge) {y, z});
b[y].push_back((edge) {x, z});
}
for (int i = 1; i <= n - 1; i++) {
int x, y; long long z;
read(x), read(y), read(z);
c[x].push_back((edge) {y, z});
c[y].push_back((edge) {x, z});
}
csize = n;
rebuild(1, 0);
dfsa(1, 0);
dfsb(1, 0);
divide(1, 0, csize);
writeln(ans);
return 0;
}