#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define F(i, a, b) for (register int i = (a); i <= (b); i++)
#define LL long long
inline int rd(void) {
int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
}
const int N = 200005;
const int T = 400005;
int tot;
struct E {
int t, x, y, sign;
friend inline bool operator < (E A, E B) { return A.t != B.t ? A.t < B.t : A.sign < B.sign; }
}Edge[T];
int n, pre[N]; vector<int> g[N];
void Parent(int x) {
for (vector<int>::iterator it = g[x].begin(); it != g[x].end(); it++)
if (pre[x] != *it) {
pre[*it] = x;
Parent(*it);
}
}
#define LC (c[x][0])
#define RC (c[x][1])
int c[N][2], par[N], siz[N], out[N]; LL sum;
inline void Up(int x) { siz[x] = siz[LC] + siz[RC] + out[x] + 1; }
inline bool Root(int x) { return c[par[x]][0] != x && c[par[x]][1] != x; }
inline void Rot(int x) {
int y = par[x], z = par[y];
int L = (c[y][1] == x), R = L^1;
if (!Root(y))
c[z][c[z][1] == y] = x;
par[x] = z;
if (c[x][R] > 0)
par[c[x][R]] = y;
c[y][L] = c[x][R];
c[x][R] = y, par[y] = x;
Up(y), Up(x);
}
inline void Splay(int x) {
for (; !Root(x); Rot(x)) {
int y = par[x], z = par[y];
if (!Root(y)) { (c[y][0] == x) ^ (c[z][0] == y) ? Rot(x) : Rot(y); }
}
}
inline void Expose(int x) {
for (int t = 0; x > 0; t = x, x = par[x]) {
Splay(x);
out[x] += siz[RC];
RC = t;
out[x] -= siz[RC];
}
}
inline void Reorder(int &x, int &y) { if (pre[y] == x) swap(x, y); }
inline void Link(int x, int y) {
// 保证 x 和 y 都是 Splay 的根
Reorder(x, y);
par[x] = y;
out[y] += siz[x];
siz[y] += siz[x];
}
inline void Cut(int x, int y) {
Reorder(x, y);
Expose(x);
Splay(x);
siz[x] -= siz[LC];
par[LC] = 0, LC = 0;
}
void Travel(int x) {
if (!x) return;
Travel(LC);
printf("%d ", x);
Travel(RC);
}
void Print(int x) { Travel(x), puts(""); }
int main(void) {
#ifndef ONLINE_JUDGE
freopen("D.in", "r", stdin);
#endif
n = rd();
F(i, 1, n-1) {
int x = rd(), y = rd(), l = rd(), r = rd();
g[x].push_back(y), g[y].push_back(x);
Edge[++tot] = (E){l, x, y, +1}, Edge[++tot] = (E){r+1, x, y, -1};
}
sort(Edge+1, Edge+tot+1);
Parent(1);
F(i, 1, n) siz[i] = 1;
F(i, 1, tot) {
int x = Edge[i].x, y = Edge[i].y, sign = Edge[i].sign;
if (sign == +1) {
Expose(x);
Splay(x);
Expose(y);
Splay(y);
sum += 1LL * siz[x] * siz[y];
Link(x, y);
}
else Cut(x, y);
}
printf("%lld\n", sum);
return 0;
}
来源: http://www.bubuko.com/infodetail-2276293.html