Codeforces #588 Div1 B. Kamil and Making a Stream

計算量を詰めるのに手間取りすぎた。
https://codeforces.com/contest/1229/problem/B

問題

根付き木が与えられる。
各頂点には整数値X[i]が設定されている。
頂点u,v間のスコアf(u,v)は、その最短パス上の頂点の設定値のGCDとする。
全頂点uとuの祖先である頂点vに対し、f(u,v)の総和を求めよ。

解法

親から順に、各頂点における根頂点までの頂点のGCDの値と登場回数をmapでもっていけばよい。
葉側から集めようとするとTLEしがち。

int N;
ll X[101010];
ll mo=1000000007;
vector<int> E[101010];
map<ll,int> D[101010];
ll ret;
void dfs(int cur,int pre,map<ll,int> M) {
	map<ll,int> M2;
	M[X[cur]]++;
	FORR(m,M) {
		ll d=__gcd(m.first,X[cur]);
		M2[d]+=m.second;
		(ret+=d*m.second)%=mo;
	}
	
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,M2);
	
}
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	map<ll,int> M;
	dfs(0,-1,M);
	cout<<ret%mo<<endl;
	
}

まとめ

葉側から集めて通らない…とうなってしまった。