题意：写一个数据结构，支持森林上：连边、删边、翻转点的颜色（黑白）、查询以某一点为根的某棵树上所有黑色点到根的距离和。$\text{点数} \leq 10^5 , \text{操作数} \leq 3 \times 10^5$
连边删边不用说就是$LCT$，而边有边权，显然需要化边为点进行操作
考虑如何维护最后一个信息。考虑$LCT$中$Splay$上的某一棵子树，$Splay$的根为$x$，其左子树为$lson$，右子树为$rson$，虚子树统一称为$son$
如果我们已经计算好了$lson,rson,son$的答案，如何计算$x$的答案？
因为$Splay$上对应原树的一条链，所以：
①$rson$与$son$中的黑点在需要经过左子树中的所有边和$x$（如果$x$代表一条边），所以答案需要加上$rson$与$son$中的黑点总数$\times\,$（$x$代表的边的边权$+lson$中的实链边权总和）
②如果$x$代表一个黑点，它需要经过左子树中的所有边，所以答案需要加上$lson$中的实链边权总和
③答案再加上$lson,rson,son$的答案即可。
所以我们需要维护子树的边权总和、黑点总数，才能够计算答案。
需要注意以下几点：
①边权总和不需要将虚子树的计算在内（显然虚子树内的点都在虚子树上传的时候计算完了答案，所以在其他点上不会产生贡献），只需要把实链的计算上去
②因为需要$makeroot$操作，所以你还要记录将左右子树反过来之后的答案，这样才能正确下传标记
③注意一点：翻转左右子树对虚子树内部答案没有影响，所以虚子树答案直接上传不经过翻转的即可
#include<bits/stdc++.h>
#define lch Tree[x].ch[0]
#define rch Tree[x].ch[1]
#define int long long
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct node{
] , size , non_size;
long long val , sumE , sumL , non_sum , sumR;
bool mark , col;
}Tree[MAXN << ];
int N , M , K , cntNode;
inline bool nroot(int x){
] == x || Tree[Tree[x].fa].ch[] == x;
}
inline bool son(int x){
] == x;
}
inline void pushup(int x){
Tree[x].size = Tree[lch].size + Tree[rch].size + Tree[x].non_size + Tree[x].col;
Tree[x].sumE = Tree[lch].sumE + Tree[rch].sumE + Tree[x].val;
Tree[x].sumL = Tree[lch].sumL + Tree[rch].sumL + Tree[x].non_sum +(Tree[rch].size + Tree[x].non_size + Tree[x].col) * (Tree[x].val + Tree[lch].sumE);
Tree[x].sumR = Tree[lch].sumR + Tree[rch].sumR + Tree[x].non_sum + (Tree[lch].size + Tree[x].non_size + Tree[x].col) * (Tree[x].val + Tree[rch].sumE);
}
inline void rotate(int x){
bool f = son(x);
];
if(nroot(y))
Tree[z].ch[son(y)] = x;
Tree[x].fa = z;
Tree[x].ch[f ^ ] = y;
Tree[y].fa = x;
Tree[y].ch[f] = w;
if(w)
Tree[w].fa = y;
pushup(y);
}
inline void reverse(int x){
Tree[x].mark ^= ;
swap(lch , rch);
swap(Tree[x].sumL , Tree[x].sumR);
}
inline void pushdown(int x){
if(Tree[x].mark){
reverse(lch);
reverse(rch);
Tree[x].mark = ;
}
}
void pushdown_all(int x){
if(nroot(x))
pushdown_all(Tree[x].fa);
pushdown(x);
}
inline void Splay(int x){
pushdown_all(x);
while(nroot(x)){
if(nroot(Tree[x].fa))
rotate(son(Tree[x].fa) == son(x) ? Tree[x].fa : x);
rotate(x);
}
pushup(x);
}
inline void access(int x){
; x ; y = x , x = Tree[x].fa){
Splay(x);
Tree[x].non_size = Tree[x].non_size + Tree[Tree[x].ch[]].size - Tree[y].size;
Tree[x].non_sum = Tree[x].non_sum + Tree[Tree[x].ch[]].sumL - Tree[y].sumL;
Tree[x].ch[] = y;
pushup(x);
}
}
inline void makeroot(int x){
access(x);
Splay(x);
reverse(x);
}
inline void split(int x , int y){
makeroot(x);
access(y);
Splay(y);
}
inline void _link(int x , int y){
makeroot(x);
makeroot(y);
Tree[y].non_size += Tree[x].size;
Tree[y].non_sum += Tree[x].sumL;
Tree[x].fa = y;
pushup(y);
}
inline void link(int x , int y , int val){
Tree[++cntNode].val = val;
_link(x , cntNode);
_link(y , cntNode);
}
inline void cut(int x , int y){
split(y , x);
if(Tree[y].fa == x){
Tree[y].ch[] = ;
pushup(y);
}
else
Tree[y].fa = Tree[Tree[y].fa].ch[] = ;
lch = Tree[lch].fa = ;
pushup(x);
}
inline void query(int x){
makeroot(x);
printf("%lld\n" , Tree[x].sumL);
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("558.in" , "r" , stdin);
freopen("558.out" , "w" , stdout);
#endif
N = read();
M = read();
K = read();
cntNode = N;
int a , b , w;
while(M--){
a = read();
b = read();
w = read();
link(a , b , w);
}
while(K--)
switch(getc()){
case 'L':
a = read();
b = read();
w = read();
link(a , b , w);
break;
case 'C':
a = read();
b = read();
cut(a , b);
break;
case 'F':
a = read();
makeroot(a);
Tree[a].col ^= ;
pushup(a);
break;
case 'Q':
query(read());
break;
}
;
}