P3258 [JLOI2014]松鼠的新家树链剖分

这个题就是一道树剖板子题，就是每走一步就把所有的经过点加一就行了。还有，我的树剖板子没问题！！！谁知道为什么板子T3个点！我不管了！反正这道题正常写A了。

题干：

题目描述

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

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

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

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

输入输出格式

输入格式：

第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an

接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

输出格式：

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例

输入样例#： 复制

输出样例#： 复制

说明

<= n <=

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

const int N = ;

struct node

{

    int l,r,nxt;

}a[ * N];

int n,len = ,lst[N];

int A[N],tree[ * N];

void add(int x,int y)

{

    a[++len].l = x;

    a[len].r = y;

    a[len].nxt = lst[x];

    lst[x] = len;

}

int f[N],dep[N],son[N],siz[N],id[N],rk[N];

int tp[N],cnt = ,lazy[ * N],vis[N];

void dfs1(int u,int fa,int depth)

{

    f[u] = fa;

    siz[u] = ;

    dep[u] = depth;

    for(int k = lst[u];k;k = a[k].nxt)

    {

        int y = a[k].r;

        if(y == fa) continue;

        dfs1(y,u,depth + );

        siz[u] += siz[y];

        if(!son[u] || siz[son[u]] < siz[y])

        son[u] = y;

    }

}

void dfs2(int u,int t)

{

    vis[u] = ;

    tp[u] = t;

    id[u] = ++cnt;

    rk[cnt] = u;

    if(!son[u])

    return;

    dfs2(son[u],t);

    for(int k = lst[u];k;k = a[k].nxt)

    {

        int y = a[k].r;

        if(y == son[u] || y == f[u] || vis[y] == ) continue;

        dfs2(y,y);

    }

}

void push_down(int o,int l,int r)

{

    if(lazy[o] != )

    {

        int mid = (l + r) >> ;

        tree[o << ] += (mid - l + ) * lazy[o];

        tree[o <<  | ] += (r - mid) * lazy[o];

        lazy[o << ] += lazy[o];

        lazy[o <<  | ] += lazy[o];

        lazy[o] = ;

    }

}

void update(int o,int l,int r,int x,int y)

{

    int mid = (l + r) >> ;

    if(l == x && r == y)

    {

        tree[o] += (r - l + );

        lazy[o] += ;

        return;

    }

    push_down(o,l,r);

    if(mid >= y)

    update(o << ,l,mid,x,y);

    else if(mid < x)

    update(o <<  | ,mid + ,r,x,y);

    else

    {

        update(o << ,l,mid,x,mid);

        update(o <<  | ,mid + ,r,mid + ,y);

    }

    tree[o] = tree[o << ] + tree[o <<  | ];

}

void update2(int x,int y)

{

    while(tp[x] != tp[y])

    {

        if(dep[tp[x]] < dep[tp[y]]) swap(x,y);

        update(,,n,id[tp[x]],id[x]);

        x = f[tp[x]];

    }

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

    update(,,n,id[x],id[y]);

}

int query(int o,int l,int r,int id)

{

    if(l == r)

    return tree[o];

    push_down(o,l,r);

    int mid = (l + r) >> ;

    if(id <= mid)

    return query(o << ,l,mid,id);

    else

    return query(o <<  | ,mid + ,r,id);

}

int main()

{

    read(n);

    duke(i,,n)

    read(A[i]);

    duke(i,,n - )

    {

        int x,y;

        read(x);read(y);

        add(x,y);

        add(y,x);

    }

    dfs1(,,);

    dfs2(,);

    /*duke(i,1,n)

    printf("%d %d\n",id[i],tp[i]);*/

//    printf("QAQ\n");

    duke(i,,n - )

    update2(A[i],A[i + ]);

    duke(i,,n)

    {

        int p = query(,,n,id[i]);

        if(A[] != i)

        p -= ;

        printf("%d\n",p);

    }

    return ;

}

顺便附赠树剖板子：

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

const int N = ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

struct edge

{

    int nxt,r;

} e[ * N];

int n,m,r,cnt;

int a[N],lst[N],p;

int f[N],d[N],siz[N],son[N],rk[N];

int top[N],id[N],tree[ * N];

int lazy[ * N],len = ;

//id新编号dfs序

void add(int x,int y)

{

    e[++len].nxt = lst[x];

    e[len].r = y;

    lst[x] = len;

}

void dfs1(int u,int fa,int depth)

{

    f[u] = fa;

    d[u] = depth;

    siz[u] = ;

    for(int k = lst[u];k;k = e[k].nxt)

    {

        int y = e[k].r;

        if(y == fa)

            continue;

        dfs1(y,u,depth + );

        siz[u] += siz[y];

        if(siz[y] > siz[son[u]] || !son[u])

        {

            son[u] = y;

        }

    }

}

void dfs2(int u,int t)

{

    top[u] = t;

    id[u] = ++cnt;

    rk[cnt] = u;

    if(!son[u])

        return;

    dfs2(son[u],t);

    for(int k = lst[u];k;k = e[k].nxt)

    {

        int y = e[k].r;

        if(y != son[u] && y != f[u])

            dfs2(y,y);

    }

}

void push_down(int o,int l,int r)

{

    if(lazy[o])

    {

        lazy[o << ] += lazy[o];

        lazy[o << ] %= p;

        lazy[o <<  | ] += lazy[o];

        lazy[o <<  | ] %= p;

        int len = (r - l + );

        tree[o << ] += lazy[o] * (len - (len >> ));

        tree[o <<  | ] += lazy[o] * (len >> );

        tree[o << ] %= p;

        tree[o <<  | ] %= p;

        lazy[o] = ;

    }

}

void build(int o,int l,int r)

{

    if(l == r)

    {

        tree[o] = a[rk[l]];

        tree[o] %= p;

        return;

    }

    int mid = (l + r) >> ;

    build(o << ,l,mid);

    build(o <<  | ,mid + ,r);

    tree[o] = tree[o << ] + tree[o <<  | ];

    tree[o] %= p;

}

void up_num(int o,int l,int r,int x,int y,int w)

{

    if(l == x && r == y)

    {

        tree[o] += w * (l - r + );

        tree[o] %= p;

        lazy[o] += w;

        lazy[o] %= p;

        return;

    }

    push_down(o,l,r);

    int mid = (l + r) >> ;

    if(mid < x)

        up_num(o <<  | ,mid + ,r,x,y,w);

    else if(mid >= y)

        up_num(o << ,l,mid,x,y,w);

    else

    {

        up_num(o << ,l,mid,x,mid,w);

        up_num(o <<  | ,mid + ,r,mid + ,y,w);

    }

    tree[o] = tree[o << ] + tree[o <<  | ];

    tree[o] %= p;

}

int query(int o,int l,int r,int x,int y)

{

    if(l == r && x == y)

    {

        return tree[o];

    }

    push_down(o,l,r);

    int mid = (l + r) >> ;

    if(mid >= y)

        return query(o << ,l,mid,x,y);

    else if(mid < x)

        return query(o <<  | ,mid + ,r,x,y);

    else

    {

        return (query(o << ,l,mid,x,mid) + query(o <<  | ,mid + ,r,mid + ,y)) % p;

    }

}

int pathquery(int x,int y)

{

    int ans = ;

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

    {

        if(d[top[x]] < d[top[y]])

            swap(x,y);

        ans += query(,,n,id[top[x]],id[x]);

        ans %= p;

        x = f[top[x]];

    }

    if(d[x] > d[y])

    swap(x,y);

    ans += query(,,n,id[x],id[y]);

    ans %= p;

    return ans;

}

void pathupdate(int x,int y,int c)

{

    // int fx = top[x],fy = top[y];

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

    {

        if(d[top[x]] < d[top[y]])

        swap(x,y);

        up_num(,,n,id[top[x]],id[x],c);

        x = f[top[x]];

        // update(id[x])

    }

    if(d[x] > d[y])

    swap(x,y);

    up_num(,,n,id[x],id[y],c);

}

int main()

{

    read(n);read(m);read(r);read(p);

    duke(i,,n)

    read(a[i]);

    duke(i,,n - )

    {

        int x,y;

        read(x);read(y);

        add(x,y);

        add(y,x);

    }

    cnt = ;

    dfs1(r,,);

    dfs2(r,r);

    cnt = ;

    build(,,n);

    duke(i,,m)

    {

        int op,x,y,z;

        read(op);

        if(op == )

        {

            read(x);read(y);read(z);

            pathupdate(x,y,z);

        }

        else if(op == )

        {

            read(x);read(y);

            printf("%d\n",pathquery(x,y));

        }

        else if(op == )

        {

            read(x);read(z);

//            cout<<x<<endl;

            up_num(,,n,id[x],id[x] + siz[x] - ,z);

        }

        else

        {

            read(x);

            printf("%d\n",query(,,n,id[x],id[x] + siz[x] - ));

        }

    }

    return ;

}

/*

5 2 24

3 7 8 0

2

5

1

1

4 2

2 2

5

5 1 3

1 3

*/

巴特西

P3258 [JLOI2014]松鼠的新家树链剖分

最新文章

热门文章

巴特西

P3258 [JLOI2014]松鼠的新家 树链剖分

最新文章

热门文章

P3258 [JLOI2014]松鼠的新家树链剖分