一道树分治……简直恶心死了……我在调代码的时候只想说：我*************************************************……
昨天听ztc讲了讲树分治，下午心血来潮想写QTREE4……写的是边分治，然后调了一晚上没调出来，后来发现换一个点作根建树就A了(COGS数据弱……)……然而交到vjudge上还是WA，早上接着调结果还调不出来，一怒之下弃坑去写比较简单的动态树分治，感觉点分治挺好写嘛……然后就换用点分治重写QTREE4，调了老半天才调出来……然而vjudge上TLE了= =
这题好像点分治边分治链分治都可以，然而点分治比边分治慢，这根本不科学……看别人写的有点分治也有边分治，然而我边分治实在调不动了……
贴一发点分治的代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=;
struct binary_heap{
priority_queue<int>q1,q2;
void push(int x){q1.push(x);}
int top(){
while(!q2.empty()&&q1.top()==q2.top()){
q1.pop();
q2.pop();
}
return q1.top();
}
int top2(){
int fir=top();
pop();
int sec=top();
push(fir);
return sec;
}
void pop(){
while(!q2.empty()&&q1.top()==q2.top()){
q1.pop();
q2.pop();
}
q1.pop();
}
void erase(int x){q2.push(x);}
int size(){return (int)q1.size()-(int)q2.size();}
bool empty(){return !size();}
}heap,q[maxn],q1[maxn][];
void build(int,int,int,int);
void dfs_getcenter(int,int,int&);
void dfs_getdis(int,int,int);
void modify(int);
vector<int>G[maxn],W[maxn];
int size[maxn]={},son[maxn]={};
int depth[maxn]={},p[maxn]={},d[maxn][],id[maxn][];
bool vis[maxn]={false},col[maxn]={false};
int n,m,white,x,y,z;
char c;
int main(){
freopen("QTREE4.in","r",stdin);
freopen("QTREE4.out","w",stdout);
scanf("%d",&n);
white=n;
for(int i=;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(y);
W[x].push_back(z);
G[y].push_back(x);
W[y].push_back(z);
}
heap.push();
build(,,n,);
scanf("%d",&m);
while(m--){
scanf(" %c",&c);
if(c=='C'){
scanf("%d",&x);
modify(x);
}
else{
if(!white)printf("They have disappeared.\n");
else if(white==)printf("0\n");
else printf("%d\n",heap.top());
}
}
return ;
}
void build(int x,int k,int s,int pr){
int u=;
dfs_getcenter(x,s,u);
vis[x=u]=true;
p[x]=pr;
depth[x]=k;
q[x].push();
if(s<=)return;
for(int i=;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
d[G[x][i]][k]=W[x][i];
p[G[x][i]]=;
dfs_getdis(G[x][i],G[x][i],k);
q[x].push(q1[G[x][i]][k].top());
}
heap.push(q[x].top()+q[x].top2());
for(int i=;i<(int)G[x].size();i++)if(!vis[G[x][i]])build(G[x][i],k+,size[G[x][i]],x);
}
void dfs_getcenter(int x,int s,int &u){
size[x]=;
son[x]=;
for(int i=;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
p[G[x][i]]=x;
dfs_getcenter(G[x][i],s,u);
size[x]+=size[G[x][i]];
if(size[G[x][i]]>size[son[x]])son[x]=G[x][i];
}
if(!u||max(s-size[x],size[son[x]])<max(s-size[u],size[son[u]]))u=x;
}
void dfs_getdis(int x,int v,int k){
q1[v][k].push(d[x][k]);
size[x]=;id[x][k]=v;
for(int i=;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
p[G[x][i]]=x;
d[G[x][i]][k]=d[x][k]+W[x][i];
dfs_getdis(G[x][i],v,k);
size[x]+=size[G[x][i]];
}
}
void modify(int x){
col[x]^=true;
if(col[x]){
if(q[x].size()>)heap.erase(q[x].top()+q[x].top2());
q[x].erase();
if(q[x].size()>)heap.push(q[x].top()+q[x].top2());
white--;
}
else{
if(q[x].size()>)heap.erase(q[x].top()+q[x].top2());
q[x].push();
if(q[x].size()>)heap.push(q[x].top()+q[x].top2());
white++;
}
for(int u=p[x],k=depth[x]-;u;u=p[u],k--){
if(col[x]){
if(q[u].size()>)heap.erase(q[u].top()+q[u].top2());
q[u].erase(q1[id[x][k]][k].top());
q1[id[x][k]][k].erase(d[x][k]);
if(!q1[id[x][k]][k].empty())q[u].push(q1[id[x][k]][k].top());
if(q[u].size()>)heap.push(q[u].top()+q[u].top2());
}
else{
if(q[u].size()>)heap.erase(q[u].top()+q[u].top2());
if(!q1[id[x][k]][k].empty())q[u].erase(q1[id[x][k]][k].top());
q1[id[x][k]][k].push(d[x][k]);
q[u].push(q1[id[x][k]][k].top());
if(q[u].size()>)heap.push(q[u].top()+q[u].top2());
}
}
}
/*
SPOJ2666 QTREE4
动态树分治，这次改用点分治。
每个重心的子树存一个堆维护到重心最远的白点，每个重心也存一个堆维护子树的答案，
重心的堆的前两大的元素就可以用来更新答案，把答案扔到一个全局堆里。
翻转时跳点分治树并修改对应子树和重心的堆，修改时顺便更新一下全局堆，
查询时O(1)取全局堆最大值即可。
*/
没调出来的边分治……也贴过来好了……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=;
struct edge{int to,w,prev;bool vis;edge():to(),w(),prev(),vis(false){}}e[maxn<<];//存新树的边，vis代表是否已被删除
struct A{//大根堆，维护答案
int x,d;
A(int x,int d):x(x),d(d){}
bool operator<(const A &a)const{return d<a.d;}
};
void dfs_prework(int);//预处理，添虚点
void addedge(int,int,int);//在新树上添一条边
void build(int,int,int);//对以x为根的子树建边分治树
void dfs_getedge(int,int,int&);//找中心边
void dfs_getdis(int,int,int,int);//求距离
void modify(int);//翻转颜色
int getans(int);//更新点x对应的堆并返回当前答案
vector<int>G[maxn],W[maxn];//原树的边
int last[maxn],len=,size[maxn]={},p[maxn]={};//建边分治树用的辅助数组
int eid[maxn],d[maxn][],id[maxn][],dir[maxn][];//在深度为k的边分治树中的距离和左右，对应的点的编号
priority_queue<A>heap,q[maxn][];//全局堆和边分治树的每个点的堆
int n,m,cnt,x,y,z,col[maxn]={},white;//记一下每个点现在的颜色，0白1黑
char c;
int main(){
freopen("QTREE4.in","r",stdin);
freopen("QTREE4.out","w",stdout);
memset(last,-,sizeof(last));
memset(eid,-,sizeof(eid));
scanf("%d",&n);
cnt=white=n;
for(int i=;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(y);
W[x].push_back(z);
G[y].push_back(x);
W[y].push_back(z);
}
dfs_prework();//getchar();getchar();
memset(p,,sizeof(p));//printf("cnt=%d\n",cnt);
cnt=;
build(,,n);
scanf("%d",&m);
while(m--){
scanf(" %c",&c);
if(c=='C'){
scanf("%d",&x);
modify(x);
}
else{
while(!heap.empty()&&getans(heap.top().x)!=heap.top().d){
//printf("heap.pop()=(%d,%d)\n",heap.top().x,heap.top().d);
x=heap.top().x;
heap.pop();
if((z=getans(x))!=<<)heap.push(A(x,z));
}
//printf("heap.size()=%d\n",heap.size());
if(!white)printf("They have disappeared.\n");
else if(white==)printf("0\n");
else printf("%d\n",max(heap.top().d,));
}
}
return ;
}
void dfs_prework(int x){//预处理，添虚点
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
p[G[x][i]]=x;
dfs_prework(G[x][i]);
}
A y(,),z(,);
queue<A>q;
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=p[x])q.push(A(G[x][i],W[x][i]));
while((int)q.size()>){
y=q.front();q.pop();
z=q.front();q.pop();
cnt++;
addedge(cnt,y.x,y.d);
addedge(y.x,cnt,y.d);
addedge(cnt,z.x,z.d);
addedge(z.x,cnt,z.d);
q.push(A(cnt,));
}
while(!q.empty()){
y=q.front();q.pop();
addedge(x,y.x,y.d);
addedge(y.x,x,y.d);
}
}
void addedge(int x,int y,int z){//在新树上添一条边
e[len].to=y;//printf("addedge(%d,%d,%d)\n",x,y,z);
e[len].w=z;
e[len].prev=last[x];
last[x]=len++;
}
void build(int x,int k,int s){//对以x为根的子树建边分治树
if(s<=)return;
int rt=++cnt;//printf("\n");printf("build(%d,%d,%d)\n",x,k,s);
dfs_getedge(x,s,eid[rt]);
int u=e[eid[rt]^].to,v=e[eid[rt]].to;//printf("id=%d u=%d v=%d w=%d\n",eid[rt],u,v,e[eid[rt]].w);
e[eid[rt]].vis=e[eid[rt]^].vis=true;
p[u]=p[v]=d[u][k]=d[v][k]=;
dfs_getdis(u,rt,k,);
dfs_getdis(v,rt,k,);
if(!q[rt][].empty()&&!q[rt][].empty()){
//printf("top=(%d,%d) w=%d\n",q[rt][0].top().d,q[rt][1].top().d,e[eid[rt]].w);
//printf("heap.push(%d,%d)\n",rt,q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w);
heap.push(A(rt,q[rt][].top().d+q[rt][].top().d+e[eid[rt]].w));
}
//else printf("EMPTY\n");
build(u,k+,s-size[v]);
build(v,k+,size[v]);
}
void dfs_getedge(int x,int s,int &id){//找中心边
size[x]=;//printf("dfs_getedge(%d,%d)\n",x,s);
for(int i=last[x];i!=-;i=e[i].prev)if(!e[i].vis&&e[i].to!=p[x]){//printf("i=%d\n",i);
p[e[i].to]=x;
dfs_getedge(e[i].to,s,id);
size[x]+=size[e[i].to];
if(id==-||max(size[e[i].to],s-size[e[i].to])<max(size[e[id].to],s-size[e[id].to]))id=i;
}
}
void dfs_getdis(int x,int rt,int k,int c){//求距离，顺便完成对对应层id和dir的标号
//printf("dfs_getdis(%d,%d,%d,%d)\n",x,rt,k,c);
if(x<=n){
//printf("q[%d][%d].push(%d,%d)\n",rt,c,x,d[x][k]);
q[rt][c].push(A(x,d[x][k]));
}
id[x][k]=rt;dir[x][k]=c;
for(int i=last[x];i!=-;i=e[i].prev)if(!e[i].vis&&e[i].to!=p[x]){//printf("i=%d\n",i);
p[e[i].to]=x;
d[e[i].to][k]=d[x][k]+e[i].w;
dfs_getdis(e[i].to,rt,k,c);
}
}
void modify(int x){//翻转颜色
if(col[x])white++;
else white--;
col[x]^=;
for(int i=;i>=;i--)if(id[x][i]){//如果是0表示深度过大不存在
getans(id[x][i]);
if(!col[x]){//原为黑色，入堆
if((q[id[x][i]][dir[x][i]].empty()||q[id[x][i]][dir[x][i]].top().d<d[x][i])&&!q[id[x][i]][dir[x][i]^].empty()){
heap.push(A(id[x][i],d[x][i]+q[id[x][i]][dir[x][i]^].top().d+e[eid[id[x][i]]].w));
//printf("heap.push(%d,%d)\n",id[x][i],d[x][i]+q[id[x][i]][dir[x][i]^1].top().d+e[eid[id[x][i]]].w);
}
//printf("q[%d][%d].push(%d,%d)\n",id[x][i],dir[x][i],x,d[x][i]);
q[id[x][i]][dir[x][i]].push(A(x,d[x][i]));
}
//否则原为白色，应当出堆，但我们只需等待这个堆被询问时再更新即可(懒惰更新)
}
}
int getans(int x){//更新点x对应的堆并返回当前答案
//printf("getans(%d)\n",x);
while(!q[x][].empty()&&col[q[x][].top().x])q[x][].pop();//更新左边的堆
while(!q[x][].empty()&&col[q[x][].top().x])q[x][].pop();//更新右边的堆
if(q[x][].empty()||q[x][].empty())return <<;//如果左右有一个为空则说明有一半没有白点
else return q[x][].top().d+q[x][].top().d+e[eid[x]].w;
}
/*
5
1 2 1
2 3 1
2 4 -1
4 5 3
100000
A
C 5
A
C 3
A
C 5
A
C 5
A
C 5
A
C 5
A
C 2
A
C 1
A
C 4
A
C 2
A
C 4
A
C 3
A
C 2
A
*/
/*
SPOJ2666 QTREE4
基本思路就是边分治，每层中心边的两个端点存一个堆维护所代表子树中所有白点的距离，
再存一个全局堆维护边分治树的每个点所产生的答案。
翻转时在边分治树上修改logn个节点的堆即可，查询直接取全局堆的最大值，O(1)。
细节问题：
1.对每个点存它在深度为k的点分治树中到中心边的距离和属于中心边的哪一边，方便修改。
2.开一个数组记录每个点当前颜色，取最大值时方便查询最大值是否合法，不合法则pop掉重新取。
*/
代码真的是错的……虽然把以1为根建树换成别的点就能过掉COGS上的数据，然而vjudge上怎么换都搞不过……
寒假准备好好搞搞动态树分治……让我挖个大坑……