首页 > 资讯 > 其他 > 正文

ZOJ 3195 LCA+RMQ+找规律

17-08-25 来源：[db:作者]

收藏我要投稿

题意

给三个点，求这三个点的相连最短距离。

题解

LCA+RMQ是模板，没什么好说的。规律的话，就是最短距离为dis[a]+dis[b]+dis[c]-dis[num[x1]]-dis[num[x2]]-dis[num[x3]]。画一下图就能发现这个规律对于所有的可能情况都是满足的。

注意事项

PE好几发，ORZ。。这种输入方式还搞Between Blank Line也是很有趣。。

代码

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker,"/STACK:102400000,102400000")
#define UP(i,l,h) for(int i=l;i=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 50010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;
struct Node {
    int to,val;

    Node(int to,int val):to(to),val(val) {}
};
int num[MAXN<<1],dep[MAXN<<1],id[MAXN],ds[MAXN];
int d[MAXN<<1][20];
vector vc[MAXN];
int n,m,c,k;

void dfs(int u,int p,int deep,int dis) {
    id[u]=k;
    ds[u]=dis;
    num[k]=u;
    dep[k++]=deep;
    int sz=vc[u].size();
    UP(i,0,sz) {
        Node nd=vc[u][i];
        if(nd.to==p)
            continue;
        dfs(nd.to,u,deep+1,dis+nd.val);
        num[k]=u;
        dep[k++]=deep;
    }
}

void rmq_init() {
    UP(i,0,k) {
        d[i][0]=i;
    }
    for(int j=1; (1<dep[d[i+(1<<(j-1))][j-1]])
                d[i][j]=d[i+(1<<(j-1))][j-1];
            else
                d[i][j]=d[i][j-1];
        }
    }
}

int rmq(int l,int r) {
    int kk=0;
    W((1<<(kk+1))<=r-l+1) {
        kk++;
    }
    if(dep[d[l][kk]]>dep[d[r-(1<

点击复制链接与好友分享!回本站首页