我是靠谱客的博主 淡淡小鸽子,最近开发中收集的这篇文章主要介绍HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

Dylans loves tree

Accepts: 49
Submissions: 262
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
Dylans有一棵
   
   
    
    N
   
   个点的树。每个点有点权。树上节点标号为
   
   
    
    1N
   
   。
他得到了
   
   
    
    Q
   
   个询问,形式如下:
①
   
   
    
    0 x y
   
   :把第
   
   
    
    x
   
   个点的点权修改为
   
   
    
    y
   
   。
②
   
   
    
    1 x y
   
   :对于
   
   
    
    xy
   
   路径上的每一种点权,是否都出现偶数次?
保证每次询问的路径上最多只有一种点权的出现次数是奇数次。


   
   
    
    1N,Q100000
   
   , 点权
   
   
    
    A[i]N
   
   ,且都 
   
   
    
    100000
   
   
输入描述
第一行一个正整数
   
   
    
    T
   
   表示数据组数(
   
   
    
    T3
   
   且最多只有一组数据
   
   
    
    N>1000
   
   )
第一行两个数
   
   
    
    NQ
   
   表示树的点数和询问个数。
接下来
   
   
    
    N1
   
   行每行一对数
   
   
    
    (x,y)
   
   表示树上的一条边。
接下来一行
   
   
    
    N
   
   个数表示每个点的点权。
接下来
   
   
    
    Q
   
   行每行三个数
   
   
    
    (opt,x,y)
   
   表示询问。
输出描述
对于每个②询问,如果全是偶数输出“-1",否则输出出现奇数次的权值。
输入样例
1
3 2
1 2
2 3
1 1 1
1 1 2
1 1 3
输出样例
-1
1
Hint
hack数据里N和Q必须小于等于10000,且对于读入的每一行末尾不应该有多余的空格。
解题:

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
const int N = 100005;
#define LL __int64
struct EDG{
    int to,next;
}edg[N*2];
int eid,head[N];
int fath[N],deep[N],top[N],num[N],son[N],p[N],pos;
void init(){
    pos=0; eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v){
    edg[eid].to=v; edg[eid].next=head[u]; head[u]=eid++;
    edg[eid].to=u; edg[eid].next=head[v]; head[v]=eid++;
}
void dfs(int u,int pre,int d){
    fath[u]=pre; num[u]=1; deep[u]=d; son[u]=-1;
    for(int i=head[u]; i!=-1; i=edg[i].next){
        int v=edg[i].to;
        if(v==pre)continue;
        dfs(v,u,d+1);
        num[u]+=num[v];
        if(son[u]==-1||num[son[u]]<num[v])
            son[u]=v;
    }
}
void getpos(int u,int root){
    top[u]=root;
    p[u]=++pos;
    if(son[u]==-1)
        return ;
    getpos(son[u],root);
    for(int i=head[u]; i!=-1; i=edg[i].next){
        int v=edg[i].to;
        if(son[u]==v||v==fath[u])
            continue;
        getpos(v,v);
    }
}
int root[N*3];  //记录当前区间内所有值的xor
int a[N];
void build(int l,int r,int k){

    if(l==r){
       root[k]=a[l];
       return ;
    }
    int m=(l+r)>>1;
    build(l,m,k<<1);
    build(m+1,r,k<<1|1);
    root[k]=root[k<<1]^root[k<<1|1];
}
void updata(int l,int r,int k,int id,int vule){
    if(l==r){
        root[k]=vule;
        return ;
    }
    int m=(l+r)>>1;
    if(id<=m)
        updata(l,m,k<<1,id,vule);
    else
        updata(m+1,r,k<<1|1,id,vule);
    root[k]=root[k<<1]^root[k<<1|1];
}
int query(int l,int r,int k,int L,int R){
    if(L<=l&&r<=R){
        return root[k];
    }
    int m=(l+r)>>1 , ans=0;
    if(L<=m)
       ans^= query(l,m,k<<1,L,R);
    if(m<R)
        ans^=query(m+1,r,k<<1|1,L,R);
    return ans;
}
void swp(int &aa,int &bb){
    int tt=aa; aa=bb; bb=tt;
}
int Operat(int u,int v){
    int fu=top[u] , fv=top[v],ans=0;
    while(fu!=fv){
        if(deep[fu]<deep[fv]){
            swp(fu,fv); swp(u,v);
        }
       ans^= query(1,pos,1,p[fu],p[u]);

       u=fath[fu]; fu=top[u];
    }
    if(deep[u]>deep[v])
        swp(u,v);
    ans^=query(1,pos,1,p[u],p[v]);

    return ans;
}

int main()
{
   int T,n,q,val[N],u,v;
   scanf("%d",&T);
   while(T--){
    scanf("%d%d",&n,&q);
    init();
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        addEdg(u,v);
    }
    for(int i=1; i<=n; i++){
        scanf("%d",&val[i]);
        val[i]++;
    }

    dfs(1,1,1);
    getpos(1,1);
    for(int i=1; i<=n; i++)
        a[p[i]]=val[i];

    build(1,pos,1);
    while(q--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)
            updata(1,pos,1,p[x],y+1);//加1
        else{
            printf("%dn",Operat(x,y)-1);//减1
        }
    }
   }
    return 0;
}


最后

以上就是淡淡小鸽子为你收集整理的HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree的全部内容,希望文章能够帮你解决HDU5274 Dylans loves tree(树链剖分)很巧的点权更新Dylans loves tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(44)

评论列表共有 0 条评论

立即
投稿
返回
顶部