(mathcal{Description})
给定 (n) 个点的一棵树，有 (1,2,3) 三种边权。一条简单有向路径 ((s,t)) 合法，当且仅当走过一条权为 (3) 的边之后，只通过了权为 (1) 的边。(m) 次询问，每次询问给定 (a,b,s,t)，表示将边 ((a,b)) 的权 (-1)（若权已为 (1) 则不变），并询问 (t) 是否能走到 (s)；有多少点能够走到 (s)。
(n,mle 3 imes 10^5)。
(mathcal{Solution})
由于是求多少点可达 (s)，考虑把路径的规则反过来：一开始只能走权为 (1) 的边，放一次“大招”（走过权为 (3) 的边）后就能任意走，但只能开一次大。问题变成求 (s) 是否可达 (t)，(s) 可达多少点。
显然，(s) 可达的点可以归为如下几类：
-
与 (s) 在同一个 (1-)联通块。
-
处于一个 (12-)联通块，且该联通块由权为 (3) 的边与 (s) 所在的 (1-)联通块相连。
考虑用并查集维护 (1-)联通块和 (12-)联通块。第一类点直接求 size 就可以了。第二类点，用每一个 (12-)联通块的根向父亲贡献，最后加上父亲对当前块的贡献即为答案。
(mathcal{Code})
/* Clearink */
#include <cstdio>
inline int rint () {
int x = 0, f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint ( Tp x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
const int MAXN = 3e5;
int n, m, ecnt = 1, head[MAXN + 5], fa[MAXN + 5], facol[MAXN + 5], rchs[MAXN + 5];
struct Edge { int to, cst, nxt; } graph[MAXN * 2 + 5];
inline void link ( const int s, const int t, const int c ) {
graph[++ ecnt] = { t, c, head[s] };
head[s] = ecnt;
}
struct DSU {
int fa[MAXN + 5], siz[MAXN + 5];
inline int operator () ( const int k ) { return find ( k ); }
inline int operator [] ( const int k ) const { return siz[k]; }
inline void init () {
for ( int i = 1; i <= n; ++ i ) {
fa[i] = i, siz[i] = 1;
}
}
inline int find ( const int x ) { return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x; }
inline bool unite ( int x, int y ) {
if ( ( x = find ( x ) ) == ( y = find ( y ) ) ) return false;
return siz[fa[x] = y] += siz[x], true;
}
} dsu[2];
inline void init ( const int u ) {
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa[u] ) {
fa[v] = u, facol[v] = graph[i].cst;
init ( v );
}
}
}
int main () {
freopen ( "sea.in", "r", stdin );
freopen ( "sea.out", "w", stdout );
n = rint (), m = rint ();
for ( int i = 1, u, v, c; i < n; ++ i ) {
u = rint (), v = rint (), c = rint ();
link ( u, v, c ), link ( v, u, c );
}
dsu[0].init (), dsu[1].init (), init ( 1 );
for ( int i = 2; i <= n; ++ i ) {
if ( facol[i] <= 2 ) dsu[1].unite ( i, fa[i] );
if ( facol[i] <= 1 ) dsu[0].unite ( i, fa[i] );
}
for ( int i = 2; i <= n; ++ i ) {
if ( facol[i] == 3 ) {
rchs[dsu[0]( fa[i] )] += dsu[1][i];
}
}
for ( int a, b, s, t; m --; ) {
a = rint (), b = rint (), s = rint (), t = rint ();
if ( fa[a] == b ) a ^= b ^= a ^= b;
if ( facol[b] == 3 ) {
-- facol[b];
rchs[dsu[0]( a )] -= dsu[1][b];
rchs[dsu[0]( fa[dsu[1]( a )] )] += dsu[1][b];
dsu[1].unite ( b, a );
} else if ( facol[b] == 2 ) {
-- facol[b];
rchs[dsu[0]( a )] += rchs[b];
dsu[0].unite ( b, a );
}
putchar ( dsu[1]( s ) == dsu[1]( t )
|| dsu[0]( fa[dsu[1]( t )] ) == dsu[0]( s )
|| dsu[1]( fa[dsu[0]( s )] ) == dsu[1]( t ) ?
'1' : '0' ), putchar ( ' ' );
wint ( dsu[1][dsu[1]( s )] + rchs[dsu[0]( s )]
+ ( facol[dsu[0]( s )] == 3 ? dsu[1][dsu[1]( fa[dsu[0]( s )] )] : 0 ) );
putchar ( '
' );
}
return 0;
}
(mathcal{Details})
考试的时候拿阳寿去肝 T2，压根没发现这题水得多 qwqwq。