题目地址：CodeChef：Gangsters of Treeland | CodeChef

题目描述

树之大陆是一个有N座城市的王国（城市从0开始标号）。城市之间有N-1条道路链接，使得两点之间恰好有一条道路（也就是说，形成一棵树形结构）。城市0是首都。
初始时，每个城市都被一个帮会所控制。村民在相邻的城市间移动，如果这两个城市不是隶属于同一个帮会的势力范围内，那么需要支付一个单位的代价。
每一年都会有新的帮会涌入首都，他们会扩张自己的势力范围。具体说来，他们会占据从首都到u路径上的所有城市（包括首都和u)。因为这个原因，来往于城市间的代价变得琢磨不定，这让村民们很苦恼。于是他们找你来帮忙。
给定一个城市u，定义f(u)为以u为根的子树中所有结点到根结点的代价的平均值。

输入输出格式

输入格式：
第一行一个整数T表示数据组数。接下来有T组数据，每组数据的第一行有一个整数N表示城市的数目。接下来的N-1行，每行有两个用空格隔开的整数Ai、Bi表示一条连接这两点的边。接下来的一行一个整数Q，表示接下来有Q组询问，每个询问包含一个字符t和一个整数u。
如果t = ‘O’，表示一个新的帮会占据了从首都到u路径上的城市。
如果t = ‘q’，表示询问f(u)。

输出格式：
对每一组询问，输出一行表示对应的答案。

输入输出样例

输入样例#1：

1
13
0 1
0 2
1 11
1 10
1 9
9 12
2 5
5 8
2 4
2 3
4 6
4 7
7
q 0
O 4
q 6
q 2
O 9
q 9
q 2

输出样例#1：

2.0000000000
1.0000000000
0.8571428571
0.5000000000
1.8571428571

说明

1≤T≤15
1≤N≤10^5
1≤Q≤10^5
数据保证所有N的总和不超过2 * 10^5。
数据保证所有Q的总和不超过2 * 10^5。

题解

我们想到，O操作其实很像LCT的access操作。我们是不是可以考虑用LCT的access来做这个题。
对于询问，我们可以考虑求和再除，求和又因为树的形态确定可以通过DFS序求子树和，可以用线段树处理。考虑一次染色对答案的影响。假如access的过程中遇到一个轻边变重边的转折点，那么这个原来重边连接的子树的答案会+1，而现在重边连接的子树答案会-1。在access的操作过程中维护这个即可。
DFS序和子树大小可以一个DFS解决，由于一开始没有相同颜色的点，我们可以直接在LCT上标记所有边都是轻边。
这次的代码写的有点乱qwq。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL; 

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'O' || c == 'q';
}

inline char readop() {
    register char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 100005, INF = 1e9;
int T, n, q, ut, vt;
char op;

std::vector<int> gra[MAXN];

int dfn[MAXN], ptn[MAXN], siz[MAXN], dep[MAXN], tot;
bool vis[MAXN];

inline void graphinit() {
    for(int i = 1; i <= n; i++) gra[i].clear();
    tot = 0;
    memset(vis, 0, sizeof(vis));
}

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

struct SGTNode {
    LL val, add;
} sgt[MAXN << 2];

inline void sgtinit(int o, int l, int r) {
    sgt[o].add = 0;
    if(l == r) {
        sgt[o].val = dep[ptn[l]];
        return;
    }
    sgtinit(lch, l, mid);
    sgtinit(rch, mid + 1, r);
    sgt[o].val = sgt[lch].val + sgt[rch].val;
}

inline void pushdown(int o, int l, int r) {
    if(sgt[o].add) {
        sgt[lch].add += sgt[o].add;
        sgt[rch].add += sgt[o].add;
        sgt[lch].val += sgt[o].add * (mid - l + 1);
        sgt[rch].val += sgt[o].add * (r - mid);
        sgt[o].add = 0;
    }
}

inline void modify(int o, int l, int r, int ll, int rr, LL v) {
    if(l >= ll && r <= rr) {
        sgt[o].add += v;
        sgt[o].val += v * (r - l + 1);
        return;
    }
    pushdown(o, l, r);
    if(ll <= mid) modify(lch, l, mid, ll, rr, v);
    if(rr > mid) modify(rch, mid + 1, r, ll, rr, v);
    sgt[o].val = sgt[lch].val + sgt[rch].val;
}

inline LL query(int o, int l, int r, int ll, int rr) {
    if(l >= ll && r <= rr) {
        return sgt[o].val;
    }
    pushdown(o, l, r);
    LL res = 0;
    if(ll <= mid) res += query(lch, l, mid, ll, rr);
    if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
    return res;
}

#undef lch
#undef rch
#undef mid

struct LCTNode {
    int ch[2], fa;
} lct[MAXN];

inline bool isleft(int p) {
    return lct[lct[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    register int fa = lct[p].fa;
    return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}

inline void rotate(int p) {
    register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
    lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
    lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
    lct[p].ch[!t] = fa; lct[fa].fa = p;
}

inline void splay(int p) {
    for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
}

inline int getsubrt(int p) {
    while(lct[p].ch[0]) p = lct[p].ch[0];
    return p;
}

inline void access(int p) {
    for(register int q = 0; p; lct[p].ch[1] = q, q = p, p = lct[p].fa) {
        splay(p);
        if(lct[p].ch[1]) {
            int ch = getsubrt(lct[p].ch[1]);
            modify(1, 1, n, dfn[ch], dfn[ch] + siz[ch] - 1, 1);
        }
        if(q) {
            int ch = getsubrt(q);
            modify(1, 1, n, dfn[ch], dfn[ch] + siz[ch] - 1, -1);
        }
    }
}

inline void dfs(int u) {
    vis[u] = true;
    dfn[u] = ++tot;
    ptn[tot] = u;
    siz[u] = 1;
    for(int v : gra[u]) {
        if(vis[v]) continue;
        dep[v] = dep[u] + 1;
        lct[v].fa = u;
        dfs(v);
        siz[u] += siz[v];
    }
}

inline void lctinit() {
    memset(lct, 0, sizeof(lct));
}

int main() {
    T = readint();
    while(T--) {
        n = readint();
        graphinit();
        lctinit();
        for(int i = 1; i < n; i++) {
            ut = readint() + 1; vt = readint() + 1;
            gra[ut].push_back(vt);
            gra[vt].push_back(ut);
        }
        dfs(1);
        sgtinit(1, 1, n);
        q = readint();
        while(q--) {
            op = readop();
            ut = readint() + 1;
            if(op == 'O') {
                access(ut);
            } else {
                printf("%.8lf\n", query(1, 1, n, dfn[ut], dfn[ut] + siz[ut] - 1) / double(siz[ut]));
            }
        }
    }
    return 0;
}