\(\mathcal{Description}\)

  OurOJ.

  给定一棵 \(n\) 个结点树，\(1\) 为根，每个 \(u\) 结点有容量 \(k_u\)。\(m\) 次操作，每次操作 \((u,c)\)，表示在 \(u\) 到根路径上的每个结点放一个颜色为 \(c\) 的小球，但若某一结点容量已满，则跳过该结点不放球。求所有操作完成后每个结点拥有小球的颜色种数。

  \(n,m\le10^5\)。

\(\mathcal{Solution}\)

  优雅的离线算法。

  首先，若 \((\forall u)(k_u\ge m)\)，有一个很显然的 DFN（虚树）+差分+BIT 的计算方法，且这种计算可以通过 std::set 做到在线。现在考虑 \(k_u\) 的限制，我们可以在每个结点的球数刚好达到限制时对它询问求到答案，即利用整体二分把每个点的询问挂到一个操作时刻之后，就做完啦。

  复杂度 \(\mathcal O(m(\log m)(\log n))\)。

/* Clearink */

#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>

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;
    if ( 9 < x ) wint ( x / 10 );
    putchar ( x % 10 ^ '0' );
}

const int MAXN = 1e5, MAXLG = 17;
int n, m, ecnt, head[MAXN + 5], vol[MAXN + 5], tmpc[MAXN + 5], ans[MAXN + 5];
int dfc, dfn[MAXN + 5], ref[MAXN + 5], dep[MAXN + 5], siz[MAXN + 5];
int stc, stn[MAXN + 5], st[2 * MAXN + 5][MAXLG + 5], lg2[MAXN * 2 + 5];
std::vector<int> pts, qry[MAXN + 5];
std::set<int> vtr[MAXN + 5];

struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
struct Event { int u, c; } evt[MAXN + 5];

struct BinaryIndexTree {
    int val[MAXN + 5];
    inline void update ( int x, const int k ) {
        for ( ; x <= n; x += x & -x ) {
            val[x] += k;
        }
    }
    inline int sum ( int x ) {
        int ret = 0;
        for ( ; x; x -= x & -x ) ret += val[x];
        return ret;
    }
    inline int sum ( const int l, const int r ) {
        return l > r ? 0 : sum ( r ) - sum ( l - 1 );
    }
} bit;

inline void link ( const int s, const int t ) {
    graph[++ ecnt] = { t, head[s] };
    head[s] = ecnt;
}

inline void init ( const int u, const int f ) {
    ref[dfn[u] = ++ dfc] = u;
    st[stn[u] = ++ stc][0] = u;
    siz[u] = 1, dep[u] = dep[f] + 1;
    for ( int i = head[u], v; i; i = graph[i].nxt ) {
        if ( ( v = graph[i].to ) ^ f ) {
            init ( v, u );
            siz[u] += siz[v], st[++ stc][0] = u;
        }
    }
}

inline void initST () {
    for ( int i = 2; i <= stc; ++ i ) lg2[i] = lg2[i >> 1] + 1;
    for ( int j = 1; 1 << j <= stc; ++ j ) {
        for ( int i = 1; i + ( 1 << j ) - 1 <= stc; ++ i ) {
            if ( dep[st[i][j - 1]] < dep[st[i + ( 1 << j >> 1 )][j - 1]] ) {
                st[i][j] = st[i][j - 1];
            } else {
                st[i][j] = st[i + ( 1 << j >> 1 )][j - 1];
            }
        }
    }
}

inline int LCA ( int u, int v ) {
    if ( ( u = stn[u] ) > ( v = stn[v] ) ) u ^= v ^= u ^= v;
    int k = lg2[v - u + 1];
    return dep[st[u][k]] < dep[st[v - ( 1 << k ) + 1][k]] ?
        st[u][k] : st[v - ( 1 << k ) + 1][k];
}

inline void markQ ( std::vector<int>& pts, const int l, const int r ) {
    if ( pts.empty () ) return ;
    if ( l == r ) {
        for ( int u: pts ) qry[l].push_back ( u );
        return pts.clear ();
    }
    int mid = l + r >> 1;
    for ( int i = l ? l : 1; i <= mid; ++ i ) bit.update ( dfn[evt[i].u], 1 );
    std::vector<int> lc, rc;
    for ( int u: pts ) {
        if ( bit.sum ( dfn[u], dfn[u] + siz[u] - 1 ) < vol[u] ) rc.push_back ( u );
        else lc.push_back ( u );
    }
    pts.clear ();
    markQ ( rc, mid + 1, r );
    for ( int i = l ? l : 1; i <= mid; ++ i ) bit.update ( dfn[evt[i].u], -1 );
    markQ ( lc, l, mid );
}

inline void addNode ( std::set<int>& vtr, const int u ) {
    auto ret ( vtr.insert ( dfn[u] ) );
    if ( !ret.second ) return ;
    bit.update ( dfn[u], 1 );
    auto it ( ret.first ); int p = -1, q = -1;
    if ( it != vtr.begin () ) {
        bit.update ( dfn[LCA ( p = ref[*-- it], u )], -1 );
        ++ it;
    }
    if ( ++ it != vtr.end () ) {
        bit.update ( dfn[LCA ( q = ref[*it], u )], -1 );
    }
    if ( ~p && ~q ) {
        bit.update ( dfn[LCA ( p, q )], 1 );
    }
}

int main () {
    freopen ( "ac.in", "r", stdin );
    freopen ( "ac.out", "w", stdout );
    n = rint ();
    for ( int i = 1, u, v; i < n; ++ i ) {
        u = rint (), v = rint ();
        link ( u, v ), link ( v, u );
    }
    for ( int i = 1; i <= n; ++ i ) {
        vol[i] = rint ();
        pts.push_back ( i );
    }
    m = rint ();
    for ( int i = 1; i <= m; ++ i ) {
        evt[i].u = rint (), tmpc[i] = evt[i].c = rint ();
    }
    std::sort ( tmpc + 1, tmpc + m + 1 );
    int mxc = std::unique ( tmpc + 1, tmpc + m + 1 ) - tmpc - 1;
    for ( int i = 1; i <= m; ++ i ) {
        evt[i].c = std::lower_bound ( tmpc + 1, tmpc + mxc + 1, evt[i].c ) - tmpc;
    }
    init ( 1, 0 ), initST ();
    markQ ( pts, 0, m );
    for ( int i = 1; i <= m; ++ i ) {
        addNode ( vtr[evt[i].c], evt[i].u );
        for ( int u: qry[i] ) ans[u] = bit.sum ( dfn[u], dfn[u] + siz[u] - 1 );
    }
    for ( int q = rint (); q --; ) wint ( ans[rint ()] ), putchar ( '\n' );
    return 0;
}

  这题 Tricks 好多啊 owo。