UOJ Logo AntiLeaf的博客

博客

QTREE4 求助dalao

2017-01-19 21:30:08 By AntiLeaf

没错,就是那道SPOJ2666 QTREE4......

那道题我写了一个多小时......调了一晚上......然而还是没调出来......

COGS上最后一组数据不过,扒下来之后对着数据调了半天也没什么进展,调不下去了......

发现把以1为根建树换成以n为根建树就行......并且随便换一个都可以(问题是就是1不行

所以......这是为啥......我实在调不出来了,跪求会动态树分治的dalao纠错......

我写的是动态边分治......

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=400010;
struct edge{int to,w,prev;bool vis;edge():to(0),w(0),prev(0),vis(false){}}e[maxn<<1];//存新树的边,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=0,size[maxn]={0},p[maxn]={0};//建边分治树用的辅助数组
int eid[maxn],d[maxn][25],id[maxn][25],dir[maxn][25];//在深度为k的边分治树中的距离和左右,对应的点的编号
priority_queue<A>heap,q[maxn][2];//全局堆和边分治树的每个点的堆
int n,m,cnt,x,y,z,col[maxn]={0},white;//记一下每个点现在的颜色,0白1黑
char c;
int main(){
    freopen("QTREE4.in","r",stdin);
    freopen("QTREE4.out","w",stdout);
    memset(last,-1,sizeof(last));
    memset(eid,-1,sizeof(eid));
    scanf("%d",&n);
    cnt=white=n;
    for(int i=1;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(1);//getchar();getchar();
    memset(p,0,sizeof(p));//printf("cnt=%d\n",cnt);
    cnt=0;
    build(1,0,n);//printf("\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))!=1<<31)heap.push(A(x,z));
            }
            //printf("heap.size()=%d\n",heap.size());
            if(!white)printf("They have disappeared.\n");
            else if(white==1)printf("0\n");
            else printf("%d\n",max(heap.top().d,0));
        }
    }
    return 0;
}
void dfs_prework(int x){//预处理,添虚点
    for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
        p[G[x][i]]=x;
        dfs_prework(G[x][i]);
    }
    A y(0,0),z(0,0);
    queue<A>q;
    for(int i=0;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()>2){
        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,0));
    }
    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<=1)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]^1].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]^1].vis=true;
    p[u]=p[v]=d[u][k]=d[v][k]=0;
    dfs_getdis(u,rt,k,0);
    dfs_getdis(v,rt,k,1);
    if(!q[rt][0].empty()&&!q[rt][1].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);
        //if(q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w>=10000)printf("%d\n",q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w);
        heap.push(A(rt,q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w));
    }
    //else printf("EMPTY\n");
    build(u,k+1,s-size[v]);
    build(v,k+1,size[v]);
}
void dfs_getedge(int x,int s,int &id){//找中心边
    size[x]=1;//printf("dfs_getedge(%d,%d)\n",x,s);
    for(int i=last[x];i!=-1;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==-1||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!=-1;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]^=1;
    for(int i=23;i>=0;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]^1].empty()){
                heap.push(A(id[x][i],d[x][i]+q[id[x][i]][dir[x][i]^1].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][0].empty()&&col[q[x][0].top().x])q[x][0].pop();//更新左边的堆
    while(!q[x][1].empty()&&col[q[x][1].top().x])q[x][1].pop();//更新右边的堆
    if(q[x][0].empty()||q[x][1].empty())return 1<<31;//如果左右有一个为空则说明有一半没有白点
    else return q[x][0].top().d+q[x][1].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掉重新取。
*/

最后那组数据太大了,我就不往上放了......

UPD: 估计是COGS数据太弱了......我到vjudge上交结果怎么换根都WA......

UPD: 改成点分治就过了......然而vjudge上TLE了......囧囧囧

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010;
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][20];
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]={0},son[maxn]={0};
int depth[maxn]={0},p[maxn]={0},d[maxn][20],id[maxn][20];
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=1;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(0);
    build(1,0,n,0);
    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==1)printf("0\n");
            else printf("%d\n",heap.top());
        }
    }
    return 0;
}
void build(int x,int k,int s,int pr){
    int u=0;
    dfs_getcenter(x,s,u);
    vis[x=u]=true;
    p[x]=pr;
    depth[x]=k;
    q[x].push(0);
    if(s<=1)return;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
        d[G[x][i]][k]=W[x][i];
        p[G[x][i]]=0;
        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=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])build(G[x][i],k+1,size[G[x][i]],x);
}
void dfs_getcenter(int x,int s,int &u){
    size[x]=1;
    son[x]=0;
    for(int i=0;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]=1;id[x][k]=v;
    for(int i=0;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()>1)heap.erase(q[x].top()+q[x].top2());
        q[x].erase(0);
        if(q[x].size()>1)heap.push(q[x].top()+q[x].top2());
        white--;
    }
    else{
        if(q[x].size()>1)heap.erase(q[x].top()+q[x].top2());
        q[x].push(0);
        if(q[x].size()>1)heap.push(q[x].top()+q[x].top2());
        white++;
    }
    for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){
        if(col[x]){
            if(q[u].size()>1)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()>1)heap.push(q[u].top()+q[u].top2());
        }
        else{
            if(q[u].size()>1)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()>1)heap.push(q[u].top()+q[u].top2());
        }
    }
}
/*
SPOJ2666 QTREE4
动态树分治,这次改用点分治。
每个重心的子树存一个堆维护到重心最远的白点,每个重心也存一个堆维护子树的答案,
重心的堆的前两大的元素就可以用来更新答案,把答案扔到一个全局堆里。
翻转时跳点分治树并修改对应子树和重心的堆,修改时顺便更新一下全局堆,
查询时O(1)取全局堆最大值即可。
*/

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。