HDOJ 5274 - Dylans loves tree

Source

BestCoder Round #45 3問目
HDOJ 5274

問題概要

$N$ ノードからなる無向木が与えられる．
また，各ノードには整数が書かれていて，最初ノード $k$ に書かれている整数は $A_k$ である．
$Q$ 個のクエリが来るので，それに答える問題．
各クエリは以下の $2$ 種類の打ちどちらか．

  1. ノード $X$ に書かれている整数を $Y$ に変更する．
  2. ノード $X$ からノード $Y$ に向かうパス上に奇数回登場する整数は高々 $1$ 個であることが保証されているので，奇数回登場する整数が存在するならそれを求め，存在しないならそれを指摘する．

解法

ノードに書かれている整数は全て $+1$ しておけば，パス上の整数に対して ${\rm XOR}$ を取れば良い．
${\rm XOR}$ が $0$ となれば，奇数回登場する整数は存在しない．
自分の解答では，Heavy-Light Decompositionして，各グループに対して ${\rm XOR}$ を取るFenwick Treeを持たせて処理を行った．
この方針だと，時間計算量は $O(N \log N + Q (\log N)^2)$ 程度．

C++によるスパゲッティなソースコード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

char memarr[67000000]; void *imem = memarr;
#define MD 1000000007

void* setUndirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++,(*es)[B[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i],(*edge)[B[i]][(*es)[B[i]]++]=A[i];return workMemory;}

template<class T>
struct fenwickXor{
  int size, memory; T *data;
  void malloc(int mem){memory=mem;data=(T*)std::malloc(sizeof(T)*mem);}
  void *malloc(int mem, void *workMemory){memory=mem;data=(T*)workMemory;return (void*)(data+mem);}
  void free(void){memory=0;free(data);}
  void init(int N){size=N;memset(data,0,sizeof(T)*N);}
  void add(int k, T val){while(k<size)data[k]^=val,k|=k+1;}
  T get(int k){T res=0;while(k>=0)res^=data[k],k=(k&(k+1))-1;return res;}
  T range(int a, int b){if(b==-1)b=size-1;return get(b)^get(a-1);}
};

struct HLD{
  int N, *es, **edge, *dep, *sz;
  int *group, *groupind, groupNum, *groupSize, **groupNode, *groupUpNode, *groupDepth;
  void* init(int N__, int *es__, int **edge__, void *mem){int i,j,k,x,y,m,*q;char*v;N=N__;es=es__;edge=edge__;dep=(int*)mem;sz=dep+N;group=sz+N;groupind=group+N;mem=groupind+N;q=(int*)mem;v=(char*)(q+N);rep(i,N)v[i]=0;x=0;y=1;q[0]=0;v[0]=1;while(x<y){i=q[x++];rep(j,es[i]){k=edge[i][j];if(!v[k])v[k]=1,q[y++]=k;}}rep(i,N)sz[i]=0;for(j=N-1;j>=0;j--){i=q[j];sz[i]=1;rep(k,es[i])sz[i]+=sz[edge[i][k]];}rep(i,N)group[i]=-1;groupNum=0;rep(j,N){i=q[j];if(group[i]>=0)continue;group[i]=groupNum++;groupind[i]=0;for(;;){m=-1;rep(k,es[i]){if(group[edge[i][k]]!=-1)continue;if(m==-1)m=k;else if(sz[edge[i][k]]>sz[edge[i][m]])m=k;}if(m==-1)break;group[edge[i][m]]=group[i];groupind[edge[i][m]]=groupind[i]+1;i=edge[i][m];}}groupSize=(int*)mem;groupUpNode=groupSize+groupNum;groupDepth=groupUpNode+groupNum;rep(i,groupNum)groupSize[i]=0;rep(i,N)groupSize[group[i]]++;groupNode=(int**)(groupDepth+groupNum);groupNode[0]=(int*)(groupNode+groupNum);REP(i,1,groupNum)groupNode[i]=groupNode[i-1]+groupSize[i-1];mem=groupNode[groupNum-1]+groupSize[groupNum-1];rep(i,N)groupNode[group[i]][groupind[i]]=i;rep(i,groupNum)groupDepth[i]=-1;groupUpNode[0]=-1;groupDepth[0]=0;rep(x,groupNum)rep(y,groupSize[x]){i=groupNode[x][y];rep(j,es[i]){k=edge[i][j];if(x!=group[k]&&groupDepth[group[k]]==-1)groupUpNode[group[k]]=i,groupDepth[group[k]]=groupDepth[x]+1;}}return mem;}
};

template<class T> struct HLD_Node_FenwickXor{
  HLD *hld;
  fenwickXor<T> *seg;

  void* init(HLD *hld__, T initval[], void *mem){int i,j;hld=hld__;seg=(fenwickXor<T>*)mem;mem=seg+hld->groupNum;rep(i,hld->groupNum){mem=seg[i].malloc(hld->groupSize[i],mem);seg[i].init(hld->groupSize[i]);if(initval!=NULL)rep(j,hld->groupSize[i])seg[i].add(j,initval[hld->groupNode[i][j]]);}return mem;}
  void add(int node, T val){seg[hld->group[node]].add(hld->groupind[node],val);}
  T getSum(int u, int v){T r=0;int X=hld->group[u],Y=hld->group[v],Z,W;while(X!=Y){if(hld->groupDepth[X]<hld->groupDepth[Y])swap(u,v),swap(X,Y);r^=seg[X].get(hld->groupind[u]);u=hld->groupUpNode[X];X=hld->group[u];}Z=hld->groupind[u];W=hld->groupind[v];r^=seg[X].range(min(Z,W),max(Z,W));return r;}
};


int T;
int N, Q;
int MODE, X, Y;
int A[100000], B[100000], val[100000];
int *es, **edge;

int main(){
  int i, j, k, res;
  void *mem;
  HLD hld;
  HLD_Node_FenwickXor<int> seg;

  reader(&T);
  while(T--){
    mem = imem;

    reader(&N,&Q);
    rep(i,N-1) reader(A+i,B+i), A[i]--, B[i]--;
    rep(i,N) reader(val+i), val[i]++;

    mem = setUndirectEdge(N, N-1, A, B, &es, &edge, mem);
    mem = hld.init(N, es, edge, mem);
    mem = seg.init(&hld, val, mem);

    while(Q--){
      reader(&MODE, &X, &Y);
      if(MODE==0){
        X--; Y++;
        seg.add(X, val[X]^Y);
        val[X] = Y;
      } else {
        res = seg.getSum(X-1, Y-1);
        writerLn(res-1);
      }
    }
  }

  return 0;
}

Current time: 2024年04月24日18時09分14秒
Last modified: 2015年06月23日08時16分55秒 (by laycrs)
Tags: Competitive_Programming Hangzhou_Dianzi_University_Online_Judge BestCoder_45 BestCoder_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：