Codeforces Good Bye 2014 D問題 - New Year Santa Network

Source

Codeforces Good Bye 2014 D問題 (1500pt)
Problem description

問題概要

$N$ ノードの無向木が与えられる.
各枝 $k$ には長さ $L_k$ が設定されている.
サンタクロースは,$3$ つの異なるノード $x,y,z$ を一様かつ独立にランダムに選び,
ノード $x$,ノード $y$,ノード $z$,ノード $x$ と選ばれたノードを一周するように移動する.
この際に移動する距離の期待値を求めたい.
しかし,枝は改修されることがわかっていて,合計 $Q$ 回だけ改修される.
各改修では,枝と改修後の長さが指定されて,その枝の長さが指定された長さに変更される.
改修では,必ず枝の長さは短くなる.
各改修の後のグラフに対して,サンタクロースが移動する距離の期待値を求める問題.

解法

まず,改修を無視して考える.
ノード $u,v$ 間の距離を $d(u,v)$ と書くと,求めるべきは,${\rm E}[d(x,y)+d(y,z)+d(z,x)]$ である.
まず,期待値の線形性より,これは,$3 {\rm E}[d(x,y)]$ と等しいので,${\rm E}[d(x,y)]$ を求めれば良い.
で,これも期待値の線形性より,各枝について,その枝のコストと,選ばれた $2$ ノードがその枝を通らないと移動できない確率を掛けて足していけば良いことになる.
そこで,各枝について,その枝を取り除いた時にできる $2$ つの連結成分の大きさを求めてやると,そのような確率を計算することができる.
これは,適当に根付き木として考えてあげて,各ノードについて,そのノードを根とするような部分木のサイズをDPっぽく求めてやれば良い.
後は,枝のコストが変更された時も,期待値の線形性で,各枝についての和に分解されているので,その枝の寄与がどれだけ変化するかを見てやれば良い.

C++のスパゲッティなコード

#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 READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

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* 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;}

int N, A[111111], B[111111], C[111111], Q;
int *es, **edge;

int depth[111111], num[111111];

void dfs(int now, int bef){
  int i, j, k;

  if(bef==-1) depth[now] = 0; else depth[now] = depth[bef] + 1;
  num[now] = 1;

  rep(i,es[now]){
    k = edge[now][i];
    if(k==bef) continue;
    dfs(k, now);
    num[now] += num[k];
  }
}

int main(){
  int i, j, k;
  double res, mul;
  void *mem = malloc(70000000);

  reader(&N);
  rep(i,N-1) reader(A+i,B+i,C+i), A[i]--, B[i]--;
  mem = setUndirectEdge(N, N-1, A, B, &es, &edge, mem);

  dfs(0, -1);
  rep(i,N-1) if(depth[A[i]] > depth[B[i]]) swap(A[i], B[i]);

  res = 0;
  rep(i,N-1){
    res += (double) C[i] * (N - num[B[i]]) * num[B[i]];
  }

  mul = 3;
  mul /= (double)N*(N-1)/2;

  reader(&Q);
  while(Q--){
    reader(&i,&k); i--;
    res -= (double) (C[i] - k) * (N - num[B[i]]) * num[B[i]];
    C[i] = k;
    printf("%.15f\n", res * mul);
  }

  myed;
  return 0;
}

Current time: 2017年11月18日11時39分22秒
Last modified: 2015年01月11日08時34分10秒 (by laycrs)
Tags: Competitive_Programming Codeforces Codeforces_Good_Bye_2014
トップページに戻る

Logged in as: unknown user (not login)

ログイン: