[Luogu] P3258 [JLOI2014]松鼠的新家

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

题目分析

树剖，树状数组维护

相邻两个计划点之间的点权++，第2~n个计划点点权-1。

Code

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN =  + ;

struct Edge {

    int nxt;

    int to;

} l[MAXN<<];

int n,root;

int head[MAXN],cnt;

int deep[MAXN],fa[MAXN],siz[MAXN],heavy[MAXN];

int id[MAXN],tot;

int a[MAXN],c[MAXN],top[MAXN];

inline void add(int x,int y) {

    cnt++;

    l[cnt].nxt = head[x];

    l[cnt].to = y;

    head[x] = cnt;

    return;

}

void dfs1(int x,int from) {

    deep[x] = deep[from] + ;

    fa[x] = from;

    int tmp = ;

    siz[x] = ;

    for(int i = head[x];i;i = l[i].nxt) {

        if(l[i].to == from) continue;

        dfs1(l[i].to,x);

        siz[x] += siz[l[i].to];

        if(siz[l[i].to] > tmp) {

            tmp = siz[l[i].to];

            heavy[x] = l[i].to;

        }

    }

    return;

}

void dfs2(int x,int tp,int from) {

    id[x] = ++tot;

    top[x] = tp;

    if(!heavy[x]) return;

    dfs2(heavy[x],tp,x);

    for(int i = head[x];i;i = l[i].nxt) {

        if(l[i].to == from || l[i].to == heavy[x]) continue;

        dfs2(l[i].to,l[i].to,x);

    }

    return;

}

inline int lowbit(int x) {

    return x & (-x);

}

inline void modify(int x,int y,int v) {

    for(int i = x;i <= n;i += lowbit(i)) c[i]+=v;

    for(int i = y+;i <= n;i += lowbit(i)) c[i]-=v;

    return;

}

inline int query(int x) {

    int res = ;

    for(int i = x;i;i -= lowbit(i)) res += c[i];

    return res;

}

inline void wayadd(int x,int y,int v) {

    while(top[x] != top[y]) {

        if(deep[top[x]] < deep[top[y]]) swap(x,y);

        modify(id[top[x]],id[x],v);

        x = fa[top[x]];

    }

    if(deep[x] > deep[y]) swap(x,y);

    modify(id[x],id[y],v);

    return;

}

int main() {

    scanf("%d",&n);

    for(int i = ;i <= n;i++) {

        scanf("%d",&a[i]);

    }

    root = a[];

    int x,y;

    for(int i = ;i < n;i++) {

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    dfs1(root,);

    dfs2(root,root,);

    for(int i = ;i < n;i++) {

        wayadd(a[i],a[i+],);

        wayadd(a[i+],a[i+],-);

    }

    for(int i = ;i <= n;i++) {

        printf("%d\n",query(id[i]));

    }

    return ;

}

巴特西

[Luogu] P3258 [JLOI2014]松鼠的新家

题目描述

题目分析

Code

最新文章

热门文章