CodeChef September 2014 Cook-Off
問題文
ノード数 $N$ の木が与えられる.
$M_1$ 個のクエリと,$M_2$ 個のクエリに答える問題.
最初に $M_1$ 個のクエリを行い,その後,$M_2$ 個のクエリを行う問題.
各辺には重みがあり,最初は重みはすべて $0$.
最初の $M_1$ 個のそれぞれのクエリでは,ノード $A,B,C,D$ が与えられるので,ノード $A,B$ 間のパスに含まれる枝のうち,ノード $C,D$ 間のパスに含まれない枝の重みを全て $+1$ する.
その後の $M_2$ 個のそれぞれのクエリでは,ノード $E,F$ が与えられるので,ノード $E,F$ 間のパスに含まれる枝の重みの和を求める.
適当な根を設定して,根付き木で考える.
ダブリングなどを用いて,LCAを計算できるようにしておき,各ノードの根からの距離も求めておく.
まず最初の $M_1$ 個のクエリを考える.
$x$ を ${\rm LCA}(A,B)$ として,パス $(A,x)$ に含まれる枝の重みを $+1$ し,$(B,x)$ に含まれる枝の重みを $+1$ する.
その中で,$(C,D)$ に含まれるものは,改めて $-1$ する.
それは,$(A,x)$ にも $(C,D)$ にも含まれる枝などを求めれば良い.
$(A,x)$ に含まれるところまで移動するために,$C$ を ${\rm LCA}(C,A)$ に置き換え,$D$ を ${\rm LCA}(D,A)$ に置き換える.
また,$C$ の根からの距離が $x$ より近い場合は,$C$ を $x$ に置き換え,$D$ に関しても同様.
すると,パス $(C,D)$ は $(A,x)$ 上になるので,その部分に含まれる枝の重みを $-1$ する.
枝の重みの変化をどのように処理するかというと,変化する部分の値のみを計算しておいて,後で累積和を求めることによって,各枝の重みを計算する.
つまり,$(A,x)$ に含まれる枝に $+1$ する場合は,$x$ に $-1$ し,$A$ に $+1$ しておく(ノード $x$ はノード $x$ から親に移動する枝の重みを保持しているとする).
$M_1$ 個のクエリが終わった時に,根からDFSして,自分を根とする部分木に含まれる値の和を求めれば良い.
また,更に累積和を取り,ある部分の和を求めれるようにしておけば,後の $M_2$ のクエリに答えることもできる.
#include<bits/stdc++.h>
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_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
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);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *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);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
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);}
void writer(ll x, char c){int s=0,m=0;char f[20];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);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
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;
}
void getDepthOfTreeDFS(int node, int bef, int *depth, int *es, int **edge){
int i, k;
rep(i,es[node]){
k=edge[node][i];
if(bef==k) continue;
depth[k] = depth[node] + 1;
getDepthOfTreeDFS(k, node, depth, es, edge);
}
}
void* getDepthOfTree(int N, int root, int *es, int **edge, int **depth, void *workMemory){
*depth = (int*)workMemory;
workMemory = (void*)((*depth)+N);
(*depth)[root] = 0;
getDepthOfTreeDFS(root, -1, *depth, es, edge);
return workMemory;
}
template<class T>
void doublingRMQBuild(T arr[], int n, int res[]){
int i, k, hf;
rep(i,n) res[i] = i;
for(k=1;;k++){
hf = (1<<(k-1)); if(hf >= n) break;
rep(i,n){
res[n*k+i] = res[n*(k-1)+i];
if(i+hf < n && arr[res[n*k+i]] > arr[res[n*(k-1)+i+hf]]) res[n*k+i] = res[n*(k-1)+i+hf];
}
}
}
template<class T>
void* doublingRMQBuild(T arr[], int n, int **res, void *workMemory){
int i, k, hf;
*res = (int*)workMemory;
rep(i,n) (*res)[i] = i;
for(k=1;;k++){
hf = (1<<(k-1)); if(hf >= n) break;
rep(i,n){
(*res)[n*k+i] = (*res)[n*(k-1)+i];
if(i+hf < n && arr[(*res)[n*k+i]] > arr[(*res)[n*(k-1)+i+hf]]) (*res)[n*k+i] = (*res)[n*(k-1)+i+hf];
}
}
return (void*)((*res)+n*k);
}
template<class T>
int doublingRMQQuery(T arr[], int n, int rmq[], int a, int b){
int dep, wid = b-a+1, A, B;
for(dep=0;(1<<(dep+1))<=wid;dep++);
A = rmq[n*dep+a];
B = rmq[n*dep+b-(1<<dep)+1];
if(arr[A] > arr[B]) A = B;
return A;
}
struct LCA{
int *depth, *vs, *id, *rmq;
int N, *es, **edge;
void dfs(int node, int bef, int dep, int *num){
int i, k;
id[node] = *num;
vs[*num] = node;
depth[(*num)++] = dep;
rep(i,es[node]){
k = edge[node][i];
if(k==bef) continue;
dfs(k, node, dep+1, num);
vs[*num] = node;
depth[(*num)++] = dep;
}
}
void* init(int N_, int root, int *es_, int **edge_, void *workMemory){
int num = 0;
N = N_;
es = es_;
edge = edge_;
depth = (int*)workMemory;
vs = depth+2*N-1;
id = vs+2*N-1;
dfs(root, -1, 0, &num);
workMemory = doublingRMQBuild(depth, 2*N-1, &rmq, (void*)(id+N));
return workMemory;
}
int get(int a, int b){
int k = doublingRMQQuery(depth, 2*N-1, rmq, min(id[a],id[b]), max(id[a],id[b]));
return vs[k];
}
int getDepth(int a, int b){
int k = doublingRMQQuery(depth, 2*N-1, rmq, min(id[a],id[b]), max(id[a],id[b]));
return depth[k];
}
};
int N, M1, M2;
int A[111111], B[111111];
int **edge, *es;
int depth[110000];
int up[110000];
ll vald[110000], val[110000];
ll sum[110000];
void dfs(int node, int bef){
int i, j, k;
val[node] = vald[node];
rep(i,es[node]){
k=edge[node][i];
if(k==bef) continue;
dfs(k, node);
val[node] += val[k];
}
}
void dfs2(int node, int bef){
int i, j, k;
sum[node] = val[node];
if(up[node]>=0) sum[node] += sum[up[node]];
rep(i,es[node]){
k=edge[node][i];
if(k==bef) continue;
dfs2(k, node);
}
}
int main(){
int i, j, k;
int a, b, c, d, x, cx, dx, z;
ll res;
LCA lca;
void *mem = malloc(100000000);
reader(&N,&M1,&M2);
rep(i,N-1){
reader(A+i,B+i);
A[i]--; B[i]--;
}
mem = setUndirectEdge(N, N-1, A, B, &es, &edge, mem);
getDepthOfTreeDFS(0, -1, depth, es, edge);
mem = lca.init(N, 0, es, edge, mem);
rep(i,N) up[i] = -1;
rep(i,N) rep(j,es[i]){
k = edge[i][j];
if(depth[k]==depth[i]-1) up[i] = k;
}
rep(i,N) vald[i] = val[i] = 0;
while(M1--){
reader(&a,&b); a--; b--;
reader(&c,&d); c--; d--;
x = lca.get(a, b);
vald[a]++; vald[b]++;
vald[x]-=2;
cx = lca.get(a, c); if(depth[cx] < depth[x]) cx = x;
dx = lca.get(a, d); if(depth[dx] < depth[x]) dx = x;
z = lca.get(cx, dx);
vald[cx]--; vald[dx]--;
vald[z]+=2;
cx = lca.get(b, c); if(depth[cx] < depth[x]) cx = x;
dx = lca.get(b, d); if(depth[dx] < depth[x]) dx = x;
z = lca.get(cx, dx);
vald[cx]--; vald[dx]--;
vald[z]+=2;
}
dfs(0,-1);
dfs2(0,-1);
// rep(i,N) printf("vald %d %lld\n",i,vald[i]);
// rep(i,N) printf("val %d %lld\n",i,val[i]);
// rep(i,N) printf("sum %d %lld\n",i,sum[i]);
while(M2--){
reader(&a,&b); a--; b--;
x = lca.get(a, b);
res = sum[a] + sum[b];
res -= 2*sum[x];
writer(res,'\n');
}
return 0;
}
Current time: 2024年04月24日19時58分03秒
Last modified: 2014年09月22日21時48分34秒 (by laycrs)
Tags: Competitive_Programming CodeChef CodeChef_CookOff CookOff_201409
トップページに戻る
Logged in as: unknown user (not login)