【BZOJ 5152】【UOJ 347】【WC 2018】通路


【タイトルリンク】
  • 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;
    }