虚树

这是一个坑...

 

给出一棵树.

每次询问选择一些点,求一些东西.这些东西的特点是,许多未选择的点可以通过某种方式剔除而不影响最终结果.

于是就有了建虚树这个技巧.....

我们可以用log级别的时间求出点对间的lca....

那么,对于每个询问我们根据原树的信息重新建树,这棵树中要尽量少地包含未选择节点. 这棵树就叫做虚树.

接下来所说的"树"均指虚树,原来那棵树叫做"原树".

构建过程如下:

按照原树的dfs序号(记为dfn)递增顺序遍历选择的节点. 每次遍历节点都把这个节点插到树上.

首先虚树一定要有一个根. 随便扯一个不会成为询问点的点作根.

维护一个栈,它表示在我们已经(用之前的那些点)构建完毕的虚树上,以最后一个插入的点为端点的DFS链.

设最后插入的点为p(就是栈顶的点),当前遍历到的点为x.我们想把x插入到我们已经构建的树上去.

求出lca(p,x),记为lca.有两种情况:

　　1.p和x分立在lca的两棵子树下.

　　2.lca是p.

　　(为什么lca不能是x?

　　 因为如果lca是x,说明dfn(lca)=dfn(x)<dfn(a),而我们是按照dfs序号遍历的,于是dfn(a)<dfn(x),矛盾.)

 对于第二种情况,直接在栈中插入节点x即可,不要连接任何边(后面会说为什么).

对于第一种情况,要仔细分析.

我们是按照dfs序号遍历的(因为很重要所以多说几遍......),有dfn(x)>dfn(p)>dfn(lca).

这说明什么呢? 说明一件很重要的事:我们已经把lca所引领的子树中,p所在的子树全部遍历完了!

　　简略的证明:如果没有遍历完,那么肯定有一个未加入的点h,满足dfn(h)<dfn(x),

　　　　　　　 我们按照dfs序号递增顺序遍历的话,应该把h加进来了才能考虑x.

这样,我们就直接构建lca引领的,p所在的那个子树. 我们在退栈的时候构建子树.

p所在的子树如果还有其它部分,它一定在之前就构建好了(所有退栈的点都已经被正确地连入树中了),就剩那条链.

如何正确地把p到lca那部分连进去呢?

设栈顶的节点为p,栈顶第二个节点为q.

重复以下操作:

　　如果dfn(q)>dfn(lca),可以直接连边q->p,然后退一次栈.

　　如果dfn(q)=dfn(lca),说明q=lca,直接连边lca->p,此时子树已经构建完毕.

　　如果dfn(q)<dfn(lca),说明lca被p与q夹在中间,此时连边lca->q,退一次栈,再把lca压入栈.此时子树构建完毕.

　　　　如果不理解这样操作的缘由可以画画图.....

最后,为了维护dfs链,要把x压入栈. 整个过程就是这样.....

AC BZOJ 2286

跑得好慢!

#include <cstdio>
#include <fstream>
#include <iostream>
 
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
 
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
 
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
typedef double db;
 
using namespace std;
 
inline int getint()
{
    int res=0;
    char c=getchar();
    bool mi=false;
    while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
    while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
    return mi ? -res : res;
}
inline ll getll()
{
    ll res=0;
    char c=getchar();
    bool mi=false;
    while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
    while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
    return mi ? -res : res;
}

//==============================================================================
//==============================================================================
//==============================================================================
//==============================================================================

const int INF=(1<<30)-1;

struct edge
{ int in; int v; edge*nxt; };
edge pool[2][1005000];
edge*et[]={pool[0],pool[1]};
edge*eds[2][255000];
void addedge(int a,int b,int v,int k)
{et[k]->in=b; et[k]->v=v; et[k]->nxt=eds[k][a]; eds[k][a]=et[k]++; }
#define FOREACH_EDGE(i,j,k) for(edge*i=eds[k][j];i;i=i->nxt)
//[0] is for original graph, [1] is for query.

int n,m;

int f[19][255000];
int mi[19][255000];
int flim=18;
int dep[255000];
int dcnt=0;
int loc[255000];
void Build(int x)
{
    loc[x]=dcnt;
    dcnt++;
    
    FOREACH_EDGE(e,x,0)
    if(e->in!=f[0][x])
    {
        f[0][e->in]=x;
        mi[0][e->in]=e->v;
        dep[e->in]=dep[x]+1;
        Build(e->in);
    }
}

void Gen()
{
    for(int d=1;d<=flim;d++)
    for(int i=0;i<n;i++)
    {
        f[d][i]=f[d-1][f[d-1][i]];
        mi[d][i]=min(mi[d-1][i],mi[d-1][f[d-1][i]]);
    }
}

int getlca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b);
    
    int d=dep[a]-dep[b];
    for(int i=flim;i>=0;i--)
    if((d>>i)&1) a=f[i][a];
    
    if(a==b) return a;
    
    for(int i=flim;i>=0;i--)
    if(f[i][a]!=f[i][b]) a=f[i][a],b=f[i][b];
    
    return f[0][a];
}

int getmin(int a,int fa)
{ 
    int res=INF;
    int d=dep[a]-dep[fa];
    for(int i=flim;i>=0;i--)
    if((d>>i)&1)
    res=min(res,mi[i][a]),a=f[i][a];
    return res;
}

int a[505000];
inline bool cmp(const int&a,const int&b)
{ return loc[a]<loc[b]; }
bool need[505000];

ll DP(int x)
{
    ll res=0;
    FOREACH_EDGE(e,x,1)
    res+=( need[e->in] ? e->v : min((ll)e->v,DP(e->in)) );
    return res;
}

void Clear(int x)
{
    FOREACH_EDGE(e,x,1) Clear(e->in);
    eds[1][x]=NULL;
}


int s[505000],st;
int main()
{
    n=getint();
    
    for(int i=1;i<n;i++)
    {
        int a=getint()-1;
        int b=getint()-1;
        int c=getint();
        addedge(a,b,c,0);
        addedge(b,a,c,0);
    }
    
    f[0][0]=0; mi[0][0]=INF; dep[0]=0;
    Build(0);
    
    Gen();
    
    int T=getint();
    while(T--)
    {
        m=getint();
        for(int i=0;i<m;i++)
        a[i]=getint()-1;
        
        sort(a,a+m,cmp);
        
        //Init Tree
        et[1]=pool[1]; //delete all edges.
        for(int i=0;i<m;i++) need[a[i]]=true;
        
        //Build new Tree
        st=0;
        s[st++]=0; //root will be always here.
        for(int i=0;i<m;i++)
        {
            int x=a[i]; 
            int lca=getlca(x,s[st-1]);
            
            while(st>1 && loc[lca]<loc[s[st-2]])
            --st,addedge(s[st-1],s[st],getmin(s[st],s[st-1]),1);
            
            if(s[st-1]!=lca)
            {
                --st,addedge(lca,s[st],getmin(s[st],lca),1);
                if(s[st-1]!=lca) s[st++]=lca;
            }
            
            if(x!=s[st-1]) s[st++]=x;
        }
        
        while(st>1)
        --st,addedge(s[st-1],s[st],getmin(s[st],s[st-1]),1);
        
        //Calculate
        printf("%lld
",DP(0));
        
        //Clear the new tree.
        for(int i=0;i<m;i++) need[a[i]]=false;
        Clear(0);
    }
    
    return 0;
}

以后写倍增LCA就按照这个写....否则更加慢........在求LCA的算法中倍增本来就是最慢的了囧......