[BZOJ 3306]树

这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。

不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。

代码：

/**************************************************************
    Problem: 3306
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2308 ms
    Memory:17544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
    if(L==R){
        minv[o]=A[L];
    }else{
        MAKE_MID;
        build_tree(LCH);
        build_tree(RCH);
        maintain(o);
    }
}
int ql,qr;
int query(SEG_STD){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        MAKE_MID;
        int ans=INF;
        if(ql<=M)
            ans=min(ans,query(LCH));
        if(qr>M)
            ans=min(ans,query(RCH));
        return ans;
    }
}
int p,v;
void update(SEG_STD){
    if(L==R){
        minv[o]=v;
    }else{
        MAKE_MID;
        if(p<=M)
            update(LCH);
        else
            update(RCH);
        maintain(o);
    }
}
inline int query(int l,int r){
    if(l<1 || l>n || r<1 || r>n)
        return INF;
    ql=l;
    qr=r;
    return query(1,1,n);
}
inline void update(int pos,int value){
    p=pos;
    v=value;
    update(1,1,n);
}
 
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
    dfs_clk++;
    tid[x]=dfs_clk;
    A[dfs_clk]=d[x];
    anc[x][0]=fa;
    dep[x]=depth;
    siz[x]=1;
    int i;
    for(i=first[x];i;i=next[i]){
        dfs(to[i],x,depth+1);
        siz[x]+=siz[to[i]];
    }
}
void process(){
    register int i,j;
    for(j=1;(1<<j)<n;j++)
        for(i=1;i<=n;i++)
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
    register int p=root,j;
    if(dep[p]<dep[x])
        return false;
    for(j=18;j>=0;j--)
        if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
            p=anc[p][j];
    return p==x;
}
int findAnc(int x,int y){
    register int j;
    for(j=18;j>=0;j--)
        if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
            y=anc[y][j];
    return y;
}
 
int getAns(int x){
    if(x==root){
        return query(1,n);
    }else{
        if(isAnc(x)){
            register int t=findAnc(x,root);
            register int l=tid[t],r=tid[t]+siz[t]-1;
            return min(query(1,l-1),query(r+1,n));
        }else{
            return query(tid[x],tid[x]+siz[x]-1);
        }
    }
}
 
int main(){
    int q,x,f;
    register int i;
    char buf[3];
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d%d",&f,&d[i]);
        if(!f){
            root=i;
        }else{
            AddEdge(f,i);
        }
    }
    memset(anc,-1,sizeof(anc));
    dfs(root,-1,0);
    process();
    build_tree(1,1,n);
    while(q--){
        scanf("%s%d",buf,&x);
        if(buf[0]=='V'){
            scanf("%d",&f);
            update(tid[x],f);
        }else{
            if(buf[0]=='Q'){
                printf("%d\n",getAns(x));
            }else{
                root=x;
            }
        }
    }
    return 0;
}

题解 BZOJ DFS序 线段树 倍增LCA Comments(1) 2016年10月12日 22:19

[POJ 1679]The Unique MST

又是一个上百行代码的题……

这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树，来判断MST的唯一性。

非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是，求出MST中待加入边两端路径上最大边，删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样，就说明MST不唯一。

代码：

#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=105,maxm=10005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int first[maxn];
int next[205],to[205],dist[205];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
inline void ClearGraph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    graph_cnt=0;
}

int anc[maxn][32],maxcost[maxn][32];
int dep[maxn];
void dfs(int x,int depth,int fa,int d){
    int i;
    dep[x]=depth;
    anc[x][0]=fa;
    maxcost[x][0]=d;
    GRAPH_REP(i,x){
        if(to[i]!=fa){
            dfs(to[i],depth+1,x,dist[i]);
        }
    }
}

int n;
inline void process(){
    register int i,j,a;
    dfs(1,0,0,0);
    for(j=1;(1<<j)<n;j++){
        REP(i,n){
            if(anc[i][j-1]!=-1){
                a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
                maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
            }
        }
    }
}

int query(int x,int y){
    register int tmp,log,i,ans=-0x7fffffff;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(i=log;i>=0;i--)
        if(dep[x]-(1<<log)>=dep[y]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
        }
    if(x==y)
        return ans;
    for(i=log;i>=0;i--)
        if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
            ans=max(ans,maxcost[y][i]);
            y=anc[y][i];
        }
    ans=max(ans,maxcost[x][0]);
    ans=max(ans,maxcost[y][0]);
    return ans;
}

int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    REP(i,n)
        p[i]=i;
    CL_ARR(rank,0);
}

struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
#define ALL_FT(x) E[x].u,E[x].v
Edge E[maxm];
int m;
bitset<maxn> Choose;
int MST(){
    register int i,ans=0,cnt=0;
    ClearGraph();
    init_set();
    Choose.reset();
    sort(E+1,E+1+m);
    REP(i,m){
        if(!is_same(ALL_FT(i))){
            Choose[i]=true;
            cnt++;
            ans+=E[i].d;
            union_set(ALL_FT(i));
            AddEdge(ALL_FT(i),E[i].d);
            AddEdge(E[i].v,E[i].u,E[i].d);
        }
        if(cnt==(n-1)){
            break;
        }
    }
    return ans;
}
int main(){
    int T;
    int u,v,d;
    register int i,ans,temp;
    bool OK;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        REP(i,m){
            scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        }
        ans=MST();
        CL_ARR(anc,-1);
        process();
        OK=true;
        REP(i,m){
            if(!Choose[i]){
                temp=query(ALL_FT(i));
                if(temp==E[i].d){
                    OK=false;
                    puts("Not Unique!");
                    break;
                }
            }
        }
        if(OK)
            printf("%d\n",ans);
    }
    return 0;
}

题解 POJ 次小生成树 倍增LCA MST Comments(0) 2016年8月30日 20:27

[BZOJ 1787]紧急集合

这个题需要一些脑洞。

给出任意三点，如果我们两两求LCA，肯定有两组相同，剩下那一组就是最优集合点了。为啥？画图理解一下吧……

代码：

/**************************************************************
    Problem: 1787
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4068 ms
    Memory:80900 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define TWO_POW(n) (1<<(n))
 
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
    d[x]=dis;
    anc[x][0]=father;
    dep[x]=depth;
    int i;
    GRAPH_REP(i,x){
        if(to[i]!=father)
            dfs(to[i],x,depth+1,dis+dist[i]);
    }
}
 
int n;
inline void InitLCA(){
    register int i,j;
    for(j=1;TWO_POW(j)<n;j++){
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                anc[i][j]=anc[anc[i][j-1]][j-1];
            }
        }
    }
}
 
int QueryLCA(int x,int y){
    register int j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;TWO_POW(log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-TWO_POW(j)>=dep[y])
            x=anc[x][j];
    if(x==y)
        return y;
    for(j=log;j>=0;j--){
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            x=anc[x][j];
            y=anc[y][j];
        }
    }
    return anc[x][0];
}
inline int make_dis(int x,int y){
    return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
 
int main(){
    int u,v,D;
    int x,y,z,QinDing;
    int m;
    register int i,j;
    scanf("%d%d",&n,&m);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v,1);
        Add_Edge(v,u,1);
    }
    memset(anc,-1,sizeof(anc));
    dfs(1,-1,0,0);
    InitLCA();
    REP(i,m){
        scanf("%d%d%d",&u,&v,&D);
        x=QueryLCA(u,v);
        y=QueryLCA(u,D);
        z=QueryLCA(v,D);
        if(x==y){
            QinDing=z;
        }else{
            if(x==z){
                QinDing=y;
            }else{
                QinDing=x;
            }
        }
        printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
    }
    return 0;
}

题解 BZOJ AHOI 省选 倍增LCA Comments(0) 2016年8月25日 17:39

[洛谷 P1967]货车运输

倍增LCA经典题……

这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……

注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！

代码：

继续阅读

题解 NOIP 并查集 MST 洛谷 倍增LCA Comments(0) 2016年4月10日 18:27

[BZOJ 2588]Count on a tree

泥萌感觉我还能说什么……

这题就是DFS序套主席树，顺便带上倍增LCA，但有两大坑点：

  1. 存放数据不一定要用long long，但输入必须要。
  2. 输出数据蛋疼，最后一行行末没回车。

代码：

继续阅读

题解 SPOJ bzoj DFS序 主席树 倍增LCA Comments(0) 2016年4月10日 13:15