题解 P3950 【部落冲突】
大家都用log^2的树状数组+树剖？那我来讲一下离线吧！
【和NOIP2016Day1T2有点类似】
首先，我们把问题抽象化一下：一棵带权树，权值一开始都是0，三种操作，1）把某条边权改为1 2）把某条边权改为0 3）求出u到v之间路径上的边权和是否为0
怎么做呢？显然可以LCT，然而题主懒得码模板。
注意到u到v之间路径上的边权和=（1到u路径上的边权和）+（1到v路径上的边权和）-2*（1到LCA(u,v)路径上的边权和）
于是我们把1个query拆成了3个query，接下来的问题就是，如何离线处理6*10^5个形如对“在第T个时间单位1到v路径上的边权和“的查询
我们跑一遍dfs，dfs的时候保存一棵线段树，维护当前节点v在所有时间上到根节点1的边权和。
从v的父亲转化到v，只需要进行关于v的父亲与v之间的战争的modify；考虑完子树v后回到v的父亲，也只需要进行同等数量反向的modify。（其实是djq不会码可持久化啦）
好吧djq蒟蒻讲不清楚，贴代码吧（一样丑）
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <locale>
#include <numeric>
#include <new>
#include <stdexcept>
#include <limits>
#include <valarray>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <bitset>
#include <algorithm>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=1e9+7;
//segment tree
int tree[1048576];
int query(int id){
id+=524288;
int ans=tree[id];
id>>=1;
while(id>0){
ans+=tree[id];
id>>=1;
}
return ans;
}
void modify(int l,int r,int v){
l+=524288;r+=524288;
while(l<r){
if(l&1)tree[l]+=v;
if(!(r&1))tree[r]+=v;
l=(l+1)>>1;
r=(r-1)>>1;
}
if(l==r)tree[l]+=v;
}
//
vector<int> G[300005];
vector<pii> qy[300005];
vector<pair<pair<pii,pii>,pii> > Q;
vector<pii> war[300005];
int dep[300005],pre[300005][20];
// lca_part
void init_dfs(int v,int par){
dep[v]=dep[par]+1;
pre[v][0]=par;
rep(k,G[v].size()){
int u=G[v][k];
if(u!=par)init_dfs(u,v);
}
}
void init_lca(int n){
rep1(i,18)rep1(j,n)
pre[j][i]=pre[pre[j][i-1]][i-1];
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int dif=dep[u]-dep[v];
rep(k,19)if(dif>>k&1)u=pre[u][k];
if(u==v)return u;
for(int k=18;k>=0;k--)
if(pre[u][k]!=pre[v][k]){
u=pre[u][k];
v=pre[v][k];
}
return pre[u][0];
}
//main part
void dfs(int v,int par){
rep(k,war[v].size())
modify(war[v][k].first,war[v][k].second,1);
rep(k,qy[v].size())qy[v][k].second=query(qy[v][k].first);
rep(k,G[v].size()){
int u=G[v][k];
if(u==par)continue;
dfs(u,v);
}
rep(k,war[v].size())
modify(war[v][k].first,war[v][k].second,-1);
}
vector<pii> w;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q;
cin>>n>>q;
rep(k,n-1){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
init_dfs(1,0);
init_lca(n);
rep(k,q){
char t;
int u,v;
cin>>t;
if(t=='C'){
cin>>u>>v;
if(dep[u]<dep[v])swap(u,v);
w.push_back(MP(u,k));
}else if(t=='U'){
cin>>u;u--;
war[w[u].first].push_back(MP(w[u].second,k));
w[u].second=-1;
}else{
cin>>u>>v;int uv=LCA(u,v);
Q.push_back(MP(MP(MP(u,qy[u].size()),MP(v,qy[v].size())),MP(uv,qy[uv].size())));
qy[u].push_back(MP(k,-1));qy[v].push_back(MP(k,-1));qy[uv].push_back(MP(k,-1));
}
}
rep(k,w.size())if(w[k].second!=-1)war[w[k].first].push_back(MP(w[k].second,q-1));
dfs(1,0);
rep(k,Q.size())cout<<(qy[Q[k].first.first.first][Q[k].first.first.second].second+
qy[Q[k].first.second.first][Q[k].first.second.second].second==
2*qy[Q[k].second.first][Q[k].second.second].second?"Yes\n":"No\n");
return 0;
}