HDU 3966 & POJ 3237 & HYSBZ 2243 & HRBUST 2064 树链剖分

树链剖分是一个很固定的套路一般用来解决树上两点之间的路径更改与查询

思想是将一棵树分成不想交的几条链并且由于dfs的顺序性给每条链上的点或边标的号必定是连着的那么每两个点之间的路径都可以拆成几条链那么就是对一群区间进行更改这时候基本是用线段树进行logn的操作

做了三道基础题都属于比较好想的也就是线段树比较麻烦需要写相当长一段时间...

HDU 3966

给出一棵树的连接状况和边的大小每次可以对a-b的路径的边的权值取反或者改变指定边的值或者求a-b路径的最大值

每次取反最大值就是原最小值*-1 这样维护下去就好

POJ 3237

给出一棵树的连接状况和点的初始值每次对a-b的路径上的点权进行加减询问单点大小

树状数组会超时只能用线段树...需要注意的是点权和边权在树链剖分的时候会有一点不同例如 u == v 是否return 等

HYSBZ 2243

总觉得以前见过的样子..

给出一棵树的连接状况和边的初始颜色每次可以对a-b的路径上的边进行更改颜色

最后求a-b路径上的颜色段个数

可以由线段树的本质来看每个区间的两个子区间都是从这个线段树一分为2

那么一个区间内有多少个颜色段数就等于他的两个子区间的颜色加起来如果子区间相邻的点颜色相同那么久减去一

可以在tr数组中记录这个区间的mlmr 即中点两边的点的颜色

每次记录下来前一条链的尾颜色和当前链的头颜色进行对比如果相同就减一

最后当f1 == f2的时候要同时对比ys1和ys2

交换uv的时候 ys1和ys2也需要交换

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<map>

#include<iostream>

#include<string>

#include<vector>

using namespace std;

#define L long long

vector<int >q[100050];

int p[100050];

int fp[100050];

int fa[100050];

int son[100050];

int deep[100050];

int top[100050];

int num[100050];

int n , m , pp;

int pos;

void init(){

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

        q[i].clear();

    }

    memset(son , -1 ,sizeof(son));

    pos = 0;

}

int in[100050];

void dfs(int u , int pre , int d){

    deep[u] = d;

    fa[u] = pre;

    num[u] = 1;

    for(int i = 0;i<q[u].size();i++){

        int v = q[u][i];

        if(v != pre){

            dfs(v,u,d+1);

            num[u] += num[v];

            if(son[u] == -1 || num[v] > num[son[u]]){

                son[u] = v;

            }

        }

    }

}

void dfs2(int u , int zx){

    top[u] = zx;

    p[u] = pos ++;

    fp[pos - 1] = u;

    if(son[u] == -1){

        return ;

    }

    dfs2(son[u],zx);

    for(int i = 0;i<q[u].size();i++){

        int v = q[u][i];

        if(v != fa[u] && v != son[u]){

            dfs2(v,v);

        }

    }

}

/**

线段树 1求一个区间内有多少个颜色 2求一个点的颜色

2直接写查询

1记录这个区间的 中间的两个的颜色

*/

struct node{

    int l,r;

    int ml;

    int mr;

    int ll ;

    int rr ;

    int mark;

    int d;

}tr[100050 * 4];

void pushup(int i){

    if(tr[i].l == tr[i].r)

        return ;

    tr[i].ll = tr[i<<1].ll;

    tr[i].rr = tr[(i<<1)|1].rr ;

    tr[i].ml = tr[i<<1].rr;

    tr[i].mr = tr[(i<<1)|1].ll ;

    tr[i].d = tr[i<<1].d + tr[(i<<1)|1].d ;

    if(tr[i<<1].rr == tr[(i<<1)|1].ll)

        tr[i].d -- ;

}

void pushdown(int i){

    if(tr[i].l == tr[i].r)return ;

    if(tr[i].mark != 0){

        tr[i<<1].mark = tr[(i<<1)|1].mark = tr[i].mark ;

        tr[i<<1].ll = tr[i<<1].rr = tr[i<<1].ml = tr[i<<1].mr = tr[i].mark;

        tr[(i<<1)|1].ll = tr[(i<<1)|1].rr = tr[(i<<1)|1].ml = tr[(i<<1)|1].mr = tr[i].mark;

        tr[i<<1].d= tr[(i<<1)|1].d = 1;

        tr[i].mark = 0;

    }

}

void crea(int i , int l , int r){

    tr[i].l = l ;

    tr[i].r = r;

    tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = tr[i].mark = 0;

    if(l == r){

        tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = in[fp[l]];

        tr[i].d = 1;

        return ;

    }

    int mid = (l + r )/ 2;

    crea(i<<1,l,mid);

    crea((i<<1)|1,mid+1,r);

    pushup(i);

}

int res ;

void upda(int i ,int l ,int r , int c){

    if(tr[i].l ==l && r == tr[i].r){

        tr[i].ml = tr[i].mr = tr[i].ll = tr[i].rr = tr[i].mark = c;

        tr[i].d = 1;

        return ;

    }

    pushdown(i);

    int mid = (tr[i].l + tr[i].r) / 2;

    if(r <= mid){

        upda(i<<1,l,r,c);

    }

    else if(l > mid){

        upda((i<<1)|1,l,r,c);

    }

    else {

        upda(i<<1,l,mid,c);

        upda((i<<1)|1,mid+1,r,c);

    }

    pushup(i);

}

int query(int i ,int l ,int r){

    if(tr[i].l == l && r == tr[i].r){

        return tr[i].d;

    }

    pushdown(i);

    int mid = (tr[i].l + tr[i].r) / 2;

    if(r <= mid){

        return query(i<<1,l,r);

    }

    else if(l > mid){

        return query((i<<1)|1,l,r);

    }

    else {

        if(tr[i].ml == tr[i].mr){

            return query(i<<1,l,mid) + query((i<<1)|1,mid+1,r) - 1;

        }

        else {

            return query(i<<1,l,mid) + query((i<<1)|1,mid+1,r);

        }

    }

}

int qu2(int i ,int pos){

    if(tr[i].l == tr[i].r){

        return tr[i].ml ;

    }

    pushdown(i);

    int mid = (tr[i].l + tr[i].r) / 2;

    if(pos <= mid){

        return qu2(i<<1,pos);

    }

    else {

        return qu2((i<<1)|1,pos);

    }

}

void did(int u , int v, int c){

    int f1 = top[u];

    int f2 = top[v];

    while(f1 != f2){

        if(deep[f1] < deep[f2]){

            swap(f1,f2);

            swap(u,v);

        }

        upda(1,p[f1],p[u],c);

        u = fa[f1];

        f1 = top[u];

    }

    if(deep[u] < deep[v]){

        swap(u,v);

    }

    upda(1,p[v],p[u],c);

}

int slpf(int u, int v){

    int ans = 0;

    int f1 = top[u];

    int f2 = top[v];

    int ys1 = -1;

    int ys2 = -1;

    while(f1 != f2){

        if(deep[f1] < deep[f2]){

            swap(u,v);

            swap(f1,f2);

            swap(ys1,ys2);

        }

        ans += query(1,p[f1],p[u]);

        if(ys1 == qu2(1,p[u])){

            ans -- ;

        }

        ys1 = qu2(1,p[f1]);

        u = fa[f1];

        f1 = top[u];

        //printf("%d\n",ans);

    }

    if(deep[u] < deep[v]){

        swap(u,v);

        swap(ys1,ys2); /// --------

    }

    ans += query(1,p[v],p[u]);

    if(ys1==qu2(1,p[u])){

        ans -- ;

    }

    if(ys2==qu2(1,p[v])){

        ans -- ;

    }

    return ans ;

}

int main(){

    //freopen("in.cpp","r",stdin);

    while(scanf("%d%d",&n,&pp)!=EOF){

        init();

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

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

        }

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

            int u , v;

            scanf("%d%d",&u,&v);

            q[u].push_back(v);

            q[v].push_back(u);

        }

        dfs(1,0,0);

        dfs2(1,1);

        crea(1,0,pos-1);

        for(int i=1;i<=pp;i++){

            char s[20];

            scanf("%s",s);

            if(s[0] == 'C'){

                int u , v, c;

                scanf("%d%d%d",&u,&v,&c);

                did(u,v,c);

            }

            else {

                int u,v;

                scanf("%d%d",&u,&v);

                printf("%d\n",slpf(u,v));

            }

        }

    }

}

感觉树链剖分的主要难点在于线段树的构造...

2017.3.18 很久后又做了一道树链剖分当然LCA也可做

询问树上路径可否组成三角形利用斐波那契的思想由于每一条路径的len<=1e9 所以当路径的条数超过64左右的时候肯定是可以的

当小于64的时候拿出来直接暴力就可以了

树链剖分中 u与top[u] 是连着的在这里用a[u]存放 u到fa[u] 的边的权值

所以top[u] -> fa[top[u]] 其实是不在 u -> f1 这条链上的但是之后会发生 u = fa[f1] 直接翻到这条边上去

所以如果top[u] -> fa[top[u]] 这个边不在路径中是会直接发生 f1 == f2 的

所以这样记录是不会出现什么问题的 QAQ

好久不写好麻烦...Orz

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<map>

#include<iostream>

#include<string>

#include<vector>

#include<queue>

using namespace std;

#define L long long

const int maxn = 100050 ;

int top[maxn] , fa[maxn] , deep[maxn] , num[maxn] , p[maxn] , fp[maxn] , son[maxn] ;

int pos ;

int n ;

int a[maxn] ;

bool can ;

vector<int > q[maxn] ;

vector<int > w[maxn] ;

vector<int > tmp ;

void init() {

    pos = 1 ;

    memset(son , -1 , sizeof(son)) ;

    for(int i = 1 ; i <= n ; i ++ ) q[i].clear() ;

    for(int i = 1 ; i <= n ; i ++ ) w[i].clear() ;

}

void dfs1(int u , int pre , int d) {

    deep[u] = d ;

    fa[u] = pre ;

    num[u] = 1 ;

    for(int i = 0 ; i < q[u].size() ; i ++ ){

        int v = q[u][i] ;

        if(v != pre) {

            a[v] = w[u][i] ;

            dfs1(v,u,d+1);

            if(son[u] == -1 || num[v] > num[son[u]]) {

                son[u] = v ;

            }

        }

    }

}

void getpos(int u , int sp) {

    top[u] = sp ;

    p[u] = pos ++ ;

    fp[p[u]] = u ;

    if(son[u] == -1) return ;

    getpos(son[u] , sp) ;

    for(int i = 0 ; i < q[u].size() ; i ++ ){

        int v = q[u][i];

        if(v != son[u] && v != fa[u]) {

            getpos(v,v) ;

        }

    }

}

void slpf(int u ,int v ) {

    int f1 = top[u] , f2 = top[v] ;

    int sl = 0 ;

    while(f1 != f2) {

        if(deep[f1] < deep[f2]) {

            swap(f1 , f2) ;

            swap(u , v) ;

        }

        sl += ( p[u] - p[f1] + 1) ;

        if(sl > 65) {

            can = false ;

            return ;

        }

        else {

            for(int i = p[f1] ; i <= p[u] ; i ++ ){

                tmp.push_back(a[fp[i]]) ;

            }

        }

        u = fa[f1] ;

        f1 = top[u] ;

    }

    if(u == v) return ;

    if(deep[u] > deep[v]) swap(u , v) ;

    sl += (p[v] - p[son[u]] + 1) ;

    if(sl > 65) {

        can = false ;

        return ;

    }

    for(int i = p[son[u]] ; i <= p[v] ; i ++ ){

        tmp.push_back(a[fp[i]]) ;

    }

}

int main(){

    while(scanf("%d" , &n) != EOF) {

        init() ;

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

            int u , v , c ;

            scanf("%d%d%d",&u,&v,&c) ;

            q[u].push_back(v) ;

            q[v].push_back(u) ;

            w[u].push_back(c) ;

            w[v].push_back(c) ;

        }

        dfs1(1,0,0) ;

        getpos(1,1) ;

        a[1] = -9999999 ;

        int query ;

        scanf("%d",&query) ;

        for(int i = 1 ; i <= query ; i ++ ){

            int u , v ;

            scanf("%d%d",&u,&v) ;

            tmp.clear() ;

            can = true ;

            slpf(u , v) ;

            if(can == false) {

                printf("Yes\n") ;

            }

            else {

                sort(tmp.begin() , tmp.end()) ;

                bool ok = false ;

                if(tmp.size() < 3) {

                }

                else {

                    for(int j = 2 ; j < tmp.size() ; j ++ ){

                        int aa = tmp[j-2] ;

                        int bb = tmp[j-1] ;

                        int cc = tmp[j] ;

                        if(aa + bb > cc) {

                            ok=true;

                            break ;

                        }

                    }

                }

                if(ok)printf("Yes\n");

                else printf("No\n") ;

            }

        }

    }

}

巴特西

HDU 3966 & POJ 3237 & HYSBZ 2243 & HRBUST 2064 树链剖分

最新文章

热门文章