自动搬运

查看原文

来自洛谷，原作者为

	Tony2 武器即是华服，战斗只作等闲；以坚硬的岩石为卧榻，以彻夜不休为睡眠

搬运于2025-08-24 22:55:19，当前版本为作者最后更新于2024-02-18 14:40:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

使用点分治，朴素地求出分治区域内所有点的信息，例如点 $u$ 的信息为 $(u_1,u_2)$ 表示从 $u$ 走到 $mid$ 可以求的所有 $win$ 值的最大值 和 $mid$ 向 $u$ 方向的那条和 $mid$ 相邻边的边权三元组 $e$。

一条路径可以表示为 $u\to mid\to v$，其中 $u$ 和 $v$ 必须属于 $mid$ 的不同子树。路径权值为 $\max(u_1,v_1,win(u_2,v_2))$。

把所有三元组放在一起跑三维偏序，至此整题得到 $O(n\log^3 n)$ 的做法。

考虑在三维偏序使用归并排序的过程。按照 $e_2$ 排序会使得相同子树的点被排到相邻位置，形成一个区间。对于同一区间内的元素不会构成路径；此时相当于归并若干个区间。按照区间长度分治归并即可。对于时间复杂度，可以注意到分治时两层长度一定减半，否则已经递归至底层；类似全局平衡二叉树的分析，整个分治树的高度为 $O(\log n)$，总时间复杂度加上 BIT 为 $O(n\log^2 n)$。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int n;
ll ans;
int a[N], b[N];
vector<pair<int, int>> e[N];
int sz[N], mx[N];
bool vis[N], vis2[N];
int ttot, tt[N];
void getrt(int u, int fa){
	tt[++ttot] = u;
	sz[u] = 1;
	mx[u] = 0;
	for (auto& [v, id] : e[u])
		if (!vis[v] && v != fa){
			getrt(v, u);
			sz[u] += sz[v];
			mx[u] = max(sz[v], mx[u]);
		}
}
int f[N];
int tot, tot2, tot3, tr[N], ed[N];
pair<int, int> A[N], B[N];
int res[N];
pair<int, int> tmp[N];
int win(int x, int y){
	if (x < y && b[x] < b[y]) return a[x];
	else if (x > y && b[x] > b[y]) return a[y];
	else return 0;
}
void dfs2(int u, int fae){
	tr[++tot] = f[u];
	for (auto& [v, id] : e[u])
		if (vis2[v] && id != fae){
			f[v] = max(f[u], win(fae, id));
			dfs2(v, id);
		}
}
struct tree2{
	int a[N];
	void add(int x, int k){
		x++;
		for (; x <= n + 1; x += x & -x)
			a[x] += k;
	}
	int ask(int x){
		x++;
		int res = 0;
		for (; x; x -= x & -x)
			res += a[x];
		return res;
	}
}T1, T2;
void dfs3(int l, int r){
	if (l == r) return;
	pair<int, int> mn(1e9, 0);
	for (int i = l; i < r; i++)
		mn = min(make_pair(abs(2 * ed[i] - ed[l - 1] - ed[r]), i), mn);
	int mid = mn.second;
//	int mid = (l + r) >> 1;
	dfs3(l, mid);
	dfs3(mid + 1, r);
	{//x2 < y2 B贡献 
		int j = ed[r];
		for (int i = ed[mid]; i > ed[l - 1]; i--){
			for (; j > ed[mid] && A[j] > B[i]; j--)
				T1.add(A[j].second, 1);
			ans += 1ll * T1.ask(B[i].second) * B[i].second;
		}
		for (int k = j + 1; k <= ed[r]; k++)
			T1.add(A[k].second, -1);
	}
	{//x2 < y2 A贡献 
		int j = ed[l - 1] + 1;
		for (int i = ed[mid] + 1; i <= ed[r]; i++){
			for (; j <= ed[mid] && B[j] < A[i]; j++)
				T1.add(B[j].second, 1);
			ans += 1ll * T1.ask(A[i].second) * A[i].second;
		}
		for (int k = ed[l - 1] + 1; k < j; k++)
			T1.add(B[k].second, -1);
	}
	{//x2 > y2 Al
		int j = ed[mid] + 1;
		for (int i = ed[l - 1] + 1; i <= ed[mid]; i++){
			for (; j <= ed[r] && A[j] < A[i]; j++)
				T1.add(A[j].second, 1);
			ans += 1ll * T1.ask(A[i].second) * A[i].second;
		}
		for (int k = ed[mid] + 1; k < j; k++)
			T1.add(A[k].second, -1);
	}
	{//x2 > y2 Ar
		int j = ed[mid];
		for (int i = ed[r]; i > ed[mid]; i--){
			for (; j > ed[l - 1] && A[j] > A[i]; j--)
				T1.add(A[j].second, 1);
			ans += 1ll * T1.ask(A[i].second) * A[i].second;
		}
		for (int k = j + 1; k <= ed[mid]; k++)
			T1.add(A[k].second, -1);
	}
	merge(A + ed[l - 1] + 1, A + ed[mid] + 1, A + ed[mid] + 1, A + ed[r] + 1, tmp + 1);
	copy(tmp + 1, tmp + 1 + ed[r] - ed[l - 1], A + ed[l - 1] + 1);
	merge(B + ed[l - 1] + 1, B + ed[mid] + 1, B + ed[mid] + 1, B + ed[r] + 1, tmp + 1);
	copy(tmp + 1, tmp + 1 + ed[r] - ed[l - 1], B + ed[l - 1] + 1);
}
void dfs1(int u){
	ttot = 0;
	getrt(u, 0);
	int S = sz[u];
	for (int i = 1; i <= ttot; i++){
		int v = tt[i];
		if (max(mx[v], S - sz[v]) * 2 <= S)
			u = v;
	}
	vis[u] = 1;
	if (S == 1){
		vis2[u] = 1;
		return;
	}
	vector<pair<int, int>> son;
	for (auto [v, id] : e[u])
		if (!vis[v]){
			son.emplace_back(v, id);
			S = sz[v];
			dfs1(v);
		}
	int len = son.size();
	tot2 = tot3 = 0;
	for (auto [v, id] : son){
		f[v] = 0;
		tot = 0;
		dfs2(v, id);
		for (int i = 1; i <= tot; i++){
			int x = tr[i];
			ans += x;
			A[tot2 + i] = {b[id], x};
			B[tot2 + i] = {b[id], max(x, a[id])};
		}
		tot2 += tot;
		ed[++tot3] = tot2;
	}
	dfs3(1, tot3);
	vis2[u] = 1;
}
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	n = read();
	for (int i = 1; i < n; i++){
		int u = read(), v = read();
		a[i] = read(), b[i] = read();
		e[u].emplace_back(v, i);
		e[v].emplace_back(u, i);
	}
	dfs1(1);
	cout << ans;
    return 0;
}