@[complete_binary_tree](/user/683859) 你写个一定不会错的LCA看先嘛
by zhuoheng @ 2024-04-03 23:39:20
我好像少开了一个set，然后假了：（
by complete_binary_tree @ 2024-04-04 08:25:24
现在好了 样例都没过 只过了 hack
```cpp
#include<bits/stdc++.h>
using namespace std;
namespace FastIO{
template<typename T>
void read(T& x);
template<typename T, typename ... Args>
void read(T& a, Args& ...b){
read(a), read(b...);
}
template<typename T>
void read(T& x){
x = 0;int f = 1;
char ch = getchar();
while((ch < '0' || ch > '9') && ch != EOF){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - 48;
ch = getchar();
}
x *= f;
return ;
}
};
using FastIO::read;
const int N = 100005;
int n;
struct node{ int to, nxt; };
struct lianshi{
int head[N];
node e[N << 1];
int cnt;
void add( int u, int v ){ e[++cnt] = { v, head[u] }; head[u] = cnt; }
operator node*(){ return e; }
} tree;
int fa[20][N], deep[N];
void dfs1( int u, int _fa ){ //初始化：fa,deep
fa[0][u] = _fa, deep[u] = deep[_fa] + 1;
for( int i = tree.head[u]; i; i = tree[i].nxt ){
int v = tree[i].to;
if( v == _fa ) continue;
dfs1( v, u );
}
return ;
}
void prelca(){ //lca的预处理
for( int i = 1; i <= 18; ++i )
for( int j = 1; j <= n; ++j )
fa[i][j] = fa[i - 1][fa[i - 1][j]];
}
int jumpup( int a, int num ){
int i = 0;
while( num ){
if( num & 1 ) a = fa[i][a];
num >>= 1, ++i;
}
return a;
}
int lca( int a, int b ){
if( a == b ) return a;
if( deep[a] > deep[b] ) swap( a, b );
b = jumpup( b, deep[b] - deep[a] );
if( a == b ) return a;
for( int i = 18; i >= 0; --i ){
if( fa[i][a] != fa[i][b] ) a = fa[i][a], b = fa[i][b];
}
return fa[0][a];
}
int dist( int a, int b ){
int _lca = lca( a, b );
return deep[a] + deep[b] - 2 * deep[_lca];
}
bool vis[N];
int fadft[N], nodft[N], jds[N], mxzs[N];
queue<int> q;
void findzx( int u, int _fa ){
jds[u] = 1, mxzs[u] = 0;
q.push( u );
for( int i = tree.head[u]; i; i = tree[i].nxt ){
int v = tree[i].to;
if( vis[v] || v == _fa ) continue;
findzx( v, u );
jds[u] += jds[v], mxzs[u] = max( mxzs[u], jds[v] );
}
return ;
}
vector<int> dft[N];
int dfz( int root, int _fa ){ //建造点分树
findzx( root, 0 );
int jd = jds[root];
while( !q.empty() ){
int u = q.front(); q.pop();
mxzs[u] = max( mxzs[u], jd - jds[u] );
if( mxzs[root] > mxzs[u] ) root = u;
}
vis[root] = 1;
for( int i = tree.head[root]; i; i = tree[i].nxt ){
int v = tree[i].to;
if( v == _fa || vis[v] ) continue;
int sonroot = dfz( v, root );
dft[root].push_back( sonroot );
fadft[sonroot] = root;
nodft[sonroot] = dft[root].size() - 1;
}
return root;
}
int root, cnt, kd[N];
multiset<pair<int, int>> st[N]; //son,dis
multiset<pair<int, int>> st2[N]; //u,dis
multiset<int> ans;
bool deng[N];
void change( int pos ){
if( !deng[pos] ){
deng[pos] = 1;
cnt++;
for( int i = pos; i; i = fadft[i] ){
// printf("!%d\n", i);
if( st[i].size() >= 2 ){
auto _end = --st[i].end(), _end2 = _end;
/*if( st[i].count( *_end ) == 1 )*/ _end2--;
ans.emplace( (*_end).first + (*_end2).first );
}
else if( st[i].size() == 1 && deng[i] ) ans.emplace( ( *st[i].begin() ).first );
if( st[fadft[i]].size() >= 2 && fadft[i] ){
auto _end = --st[fadft[i]].end(), _end2 = _end;
/*if( st[fadft[i]].count( *_end ) == 1 )*/ _end2--;
auto er = ans.find( (*_end).first + (*_end2).first );
ans.erase( er );
}
else if( st[fadft[i]].size() == 1 && deng[fadft[i]] && fadft[i] ){ auto er = ans.find( ( *st[fadft[i]].begin() ).first ); ans.erase( er );}
if( st2[i].size() ){ auto er = st[fadft[i]].find( make_pair( ( *( --st2[i].end() ) ).first, nodft[i] ) ); if( er != st[fadft[i]].end() ) st[fadft[i]].erase( er ); }
st2[i].emplace( make_pair( dist( pos, i ), pos ) );
st[fadft[i]].emplace( make_pair( dist( pos, fadft[i] ), nodft[i] ) );
kd[i]++;
}
}
else{
deng[pos] = 0;
cnt--;
for( int i = pos; i; i = fadft[i] ){
// printf("!%d", i);
if( st[i].size() >= 2 ){
auto _end = --st[i].end(), _end2 = _end;
/*if( st[i].count( *_end ) == 1 )*/ _end2--;
ans.emplace( (*_end).first + (*_end2).first );
}
else if( st[i].size() == 1 && deng[i] ) ans.emplace( ( *st[i].begin() ).first );
if( st[fadft[i]].size() >= 2 && fadft[i] ){
auto _end = --st[fadft[i]].end(), _end2 = _end;
/*if( st[fadft[i]].count( *_end ) == 1 )*/ _end2--;
auto er = ans.find( (*_end).first + (*_end2).first );
ans.erase( er );
}
else if( st[fadft[i]].size() == 1 && deng[fadft[i]] && fadft[i] ){ auto er = ans.find( ( *st[fadft[i]].begin() ).first ); ans.erase( er ); }
auto er1 = st2[i].find( make_pair( dist( pos, i ), pos ) ), er2 = st[fadft[i]].find( make_pair( dist( pos, fadft[i] ), nodft[i] ) );
if( er1 != st2[i].end() ) st2[i].erase( er1 );
if( er2 != st[fadft[i]].end() ) st[fadft[i]].erase( er2 );
kd[i]--;
if( st2[i].size() ) st[fadft[i]].emplace( make_pair( ( *( --st2[i].end() ) ).first, fadft[i] ) );
}
}
}
//int root;
/*int query(){
int ans = 0;
if( cnt <= 0 ) return -1;
if( cnt == 1 ) return 0;
for( int i = root; i; ){
// printf("!%d\n", i);
if( st[i].size() == 0 ) break;
if( st[i].size() == 1 ){
if( deng[i] ) ans = max( ans, (*st[i].begin()).first );
i = dft[i][(*st[i].begin()).second];
continue;
}
auto _end = --st[i].end();
ans = max( ans, (*_end).first + (*(--_end)).first );
// _end = --st[i].end();
// printf("-%d %d\n", (*_end).first, (*(--_end)).first);
i = dft[i][(*(--st[i].end())).second];
}
return ans;
}*/
int qu;
namespace debug{
void print( int u = 0 ){
if( u == 0 ){ for( int i = 1; i <= n; ++i ) print( i ); return ; }
putchar( '!' );
for( auto i : st[u] ) printf("(%d %d) ", i.first, i.second );
puts("");
putchar( '!' );
for( auto i : st2[u] ) printf("(%d %d) ", i.first, i.second );
puts("");
}
};
int main(){
read( n );
for( int i = 1; i < n; ++i ){
int u, v;
read( u, v );
tree.add( u, v ), tree.add( v, u );
}
dfs1( 1, 0 );
prelca();
root = dfz( 1, 0 );
for( int i = 1; i <= n; ++i ) change( i );
read( qu );
// printf("%d", dist(2, 6));
while( qu-- ){
char ch;
cin >> ch;
if( ch == 'G' ){
if( cnt == 0 ){
printf( "-1\n" );
continue;
}
else if( cnt == 1 ){
printf("0\n");
continue;
}
printf( "%d\n", *(--ans.end()) );
// for( auto i : ans ) printf( "%d ", i );
// puts("");
}
else{
int x;
read( x );
change( x );
// debug::print();
}
}
return 0;
}
/*
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
*/
```
by complete_binary_tree @ 2024-04-04 10:48:31