(mathcal{Description})
Link.
给定一棵 (n) 个点的树和 (q) 次加边操作。求出每次操作后，满足 (u,v,w) 互不相等，路径 ((u,w)) 与 ((v,w)) 无重复边的有序三元组 ((u,v,w)) 的个数。
(n,qle10^5)。
(mathcal{Solution})
考虑原树上，以某个点为 (w) 的贡献。记 (operatorname{contr}(u)) 为 (u) 的贡献，则有：
[operatorname{contr}(u)=(n-1)(n-1)-sum_{vin son_u}siz_v^2-(n-siz_u)(n-siz_u)
]
又发现一个边双中的每个点都应是等价的。所以对于以 (u) 为顶点的边双，维护 (val_u=sum_{vin son_u}siz_v^2) 和大小 (s_u)，我们也能求出它的贡献：
[operatorname{contr}(u)=s_u((n-s_u)^2-val_u-(n-siz_u)^2)+2s_u(s_u-1)(n-s_u)+s_u(s_u-1)(s_u-2)
]
加边时，暴力爬树，并用并查集维护连通边双即可。
复杂度 (mathcal O(nlog n))（并查集不带启发式合并）。
(mathcal{Code})
#include <cstdio>
#include <assert.h>
typedef long long LL;
const int MAXN = 1e5;
int n, ecnt, head[MAXN + 5];
int fa[MAXN + 5], dep[MAXN + 5], siz[MAXN + 5], blk[MAXN + 5];
LL ans, val[MAXN + 5];
struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
inline void link ( const int s, const int t ) {
graph[++ ecnt] = { t, head[s] };
head[s] = ecnt;
}
inline char fgc () {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread ( p = buf, 1, 1 << 17, stdin ), p == q ) ? EOF : *p ++;
}
inline int rint () {
int x = 0; char d = fgc ();
for ( ; d < '0' || '9' < d; d = fgc () );
for ( ; '0' <= d && d <= '9'; d = fgc () ) x = x * 10 + ( d ^ '0' );
return x;
}
inline void wint ( const LL x ) {
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
struct DSU {
int fa[MAXN + 5];
inline void init () { for ( int i = 1; i <= n; ++ i ) fa[i] = i; }
inline int find ( const int x ) { return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x; }
inline bool unite ( int x, int y ) {
x = find ( x ), y = find ( y );
return x ^ y ? fa[x] = y, true : false;
}
} dsu;
inline void init ( const int u ) {
siz[u] = blk[u] = 1;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa[u] ) {
dep[v] = dep[fa[v] = u] + 1, init ( v );
siz[u] += siz[v];
val[u] += 1ll * siz[v] * siz[v];
}
}
}
inline void calc ( const int u, const int k ) {
assert ( u == dsu.fa[u] );
int s = blk[u];
ans += 1ll * k * s * ( 1ll * ( n - s ) * ( n - s ) - val[u] - 1ll * ( n - siz[u] ) * ( n - siz[u] ) );
ans += 2ll * k * s * ( s - 1 ) * ( n - s );
ans += 1ll * k * s * ( s - 1 ) * ( s - 2 );
}
inline void merge ( const int u, const int v ) {
assert ( u == dsu.fa[u] && v == dsu.fa[v] && dep[u] < dep[v] );
calc ( u, -1 ), calc ( v, -1 );
val[u] -= 1ll * siz[v] * siz[v], val[u] += val[v], blk[u] += blk[v];
calc ( u, 1 ), dsu.unite ( v, u );
}
int main () {
n = rint (), dsu.init ();
for ( int i = 1, u, v; i < n; ++ i ) {
u = rint (), v = rint ();
link ( u, v ), link ( v, u );
}
init ( 1 );
for ( int i = 1; i <= n; ++ i ) calc ( i, 1 );
wint ( ans ), putchar ( '
' );
for ( int q = rint (), u, v; q --; ) {
u = rint (), v = rint ();
while ( dsu.find ( u ) ^ dsu.find ( v ) ) {
if ( dep[dsu.find ( u )] < dep[dsu.find ( v )] ) u ^= v ^= u ^= v;
u = dsu.find ( u );
merge ( dsu.find ( fa[u] ), u );
}
wint ( ans ), putchar ( '
' );
}
return 0;
}