A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4539: [Hnoi2016]树 树上倍增 线段树 分类讨论
发表于: | 分类: Oi | 评论:0 | 阅读:69

我真是服了湖南选手了……这题考试能A实在是太厉害了……

首先要注意读题,他每一次在下面复制的是原树原树原树……

然后就好办了,我们把一个复制粘出来的东西作为一个点插♂在树上就行了

然后把这条边的边权设为实际的距离。

最后询问的时候讨论一下,如果他俩在一个块里,那么就直接化成原树的序号,然后在原树里面求就成

如果不在一个块里,我们就先倍增求出来两个点在“外面”跨过的距离,然后再求出两个点分别到他们块内的那个“根”的距离,然后再求lca块内到真正lca的距离,当然这个距离是和一个块内计算距离是一样的了。当然有可能一块已经是另一块的祖先了,所以需要特判特判再特判

然后一个细节是如何才能化成原树的序号,显然我们需要知道他是哪个块里的,然后求个第K小就行了,求子树第K小这个工作显然是一个主席树+DFS序就能搞定的了

时间复杂度$O(n\log{n})$

常数奇大注意long long

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+5;
const int M = N << 2;
const int Max = 2200000;

int root[N], from[N], idx, dfn[N], out[N];
int n, m, q;

LL cnt[N], nn;

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct seg {
    int ls[Max],rs[Max],root[N];
    int tr[Max], sz;
    inline void insert(int x,int &y,int l,int r,int pos,int val) {
        y = ++sz;ls[y] = ls[x], rs[y] = rs[x], tr[y] = tr[x] + val;
        if(l==r) return; int mid = (l+r) >> 1;
        if(pos <= mid) insert(ls[x],ls[y],l,mid,pos,val);
        else insert(rs[x],rs[y],mid+1,r,pos,val);
    }
    void insert(int x,int val) {
        insert(root[x-1],root[x],1,n,val,1);
    }
    int ask(int x,int y,int l,int r,int kth) {
        if(l==r) return l; int mid  = (l+r) >> 1;
        int tmp = tr[ls[y]] - tr[ls[x]];
        if(tmp >= kth) return ask(ls[x],ls[y],l,mid,kth);
        else return ask(rs[x],rs[y],mid+1,r,kth - tmp);
    }
    inline int ask(int x,int y,int kth) {
        return ask(root[x-1],root[y],1,n,kth);
    }
}T;

struct Graph{
    int head[N],fa[N][20], size[N], depth[N];
    LL dis[N];

    struct graph{
        int next,to;
        LL val;
        graph () {}
        graph (int _next,int _to,LL _val)
        :next(_next),to(_to),val(_val){}
    }edge[M];

    inline void add(int x,int y,LL z){
        static int cnt = 0;
        edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
        edge[++cnt] = graph(head[y],x,z); head[y] = cnt;
    }

    void DFS(int x) {
        for(int i=1;i<=19;++i) fa[x][i] = fa[fa[x][i-1]][i-1];
        for(int i=head[x];i;i=edge[i].next) {
            if(edge[i].to != fa[x][0]) {
                fa[edge[i].to][0] = x;
                depth[edge[i].to] = depth[x] + 1;
                dis[edge[i].to] = dis[x] + edge[i].val;
                DFS(edge[i].to);
            }
        }
    }

    void DFS2(int x) {
        static int cnt = 0; size[x] = 1;
        T.insert(dfn[x] = ++cnt,x);
        for(int i=head[x];i;i=edge[i].next) {
            if(edge[i].to != fa[x][0]) {
                DFS2(edge[i].to);
                size[x] += size[edge[i].to];
            }
        }
        out[x] = cnt;
    }

    inline int lca(int x,int y) {
        if(depth[x] < depth[y]) swap(x,y);
        int tt = depth[x] - depth[y];
        for(int i=19;~i;--i) if((1<<i)&tt) x = fa[x][i];
        for(int i=19;~i;--i) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
        return x == y ? x : fa[x][0];
    }

    inline LL calc(int x,int y) {
        return dis[x] + dis[y] - (dis[lca(x,y)]<< 1) ;
    }

    inline int up(int x,int y) {
        int tt = depth[x] - depth[y] - 1;
        for(int i=19;~i;--i) if((1<<i)&tt) x = fa[x][i];
        return x;
    }
}ori,g;

inline int get(LL x) {
    return lower_bound(cnt+1,cnt+idx+1,x) - cnt;
}

LL Query(LL a,LL b) {
    int ida = get(a), rta = root[ida], aa = T.ask(dfn[rta],out[rta],a-cnt[ida-1]);
    int idb = get(b), rtb = root[idb], bb = T.ask(dfn[rtb],out[rtb],b-cnt[idb-1]);
    int lca = g.lca(ida,idb);
    if(ida == idb) return ori.calc(aa,bb);
    LL res = g.calc(ida,idb) + ori.dis[aa] - ori.dis[rta] + ori.dis[bb] - ori.dis[rtb];
    if(ida == lca) {
        int tmpb = from[g.up(idb,lca)];
        res -= ori.dis[aa] + ori.dis[tmpb] - ori.calc(aa,tmpb) - 2 * ori.dis[rta];
    }
    else if(idb == lca) {
        int tmpa = from[g.up(ida,lca)];
        res -= ori.dis[bb] + ori.dis[tmpa] - ori.calc(bb,tmpa) - 2 * ori.dis[rtb];
    }
    else {
        int tmpa = from[g.up(ida,lca)], 
            tmpb = from[g.up(idb,lca)];
        res -= ori.dis[tmpa] + ori.dis[tmpb] - ori.calc(tmpa,tmpb) - 2*ori.dis[root[lca]];
    }
    return res;
}

int Q;

int main() {
//  freopen("4539.in","r",stdin);
    n = read(), m = read(), Q = read();
    LL x,y;
    for(int i=1;i<n;++i) { x = read(), y = read(); ori.add(x,y,1); }
    ori.DFS(1);
    ori.DFS2(1);
    nn = n, cnt[1] = nn, root[1] = idx = 1;
    for(int i=2;i<=m+1;++i) {
        x = read(), y = read();
        int id = get(y), rt = root[id];
        root[i] = x, idx = i, from[i] = T.ask(dfn[rt],out[rt],y-cnt[id-1]);
        g.add(i,id,ori.dis[from[i]] - ori.dis[rt] + 1);
//      cout << from[i] << endl;
//      cout << i <<" " << id << " " << ori.dis[from[i]] - ori.dis[rt] + 1 << endl;
        nn += ori.size[x], cnt[i] = nn;
    }
    g.DFS(1);
    for(int i=1;i<=Q;++i) {
        x = read(), y = read();
        printf("%lld\n",Query(x,y));
    }
}


Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP