kmjp's blog

競技プログラミング参加記です

Codeforces #580 Div1 D. Almost All

解法を見てしまうと簡単な問題。
https://codeforces.com/contest/1205/problem/D

問題

木を成すN頂点の無向グラフが与えられる。
各辺に非負整数を設定し、頂点対間の距離として1~floor(2*N^2/9)が全通り現れるようにせよ。

解法

まず重心を求めよう。
そこから1つの木に対し1~Aまでの値が作れる場合、別の木で(A+1),2*(A+1),…B*(A+1)までを作れるようにすれば結果(A+1)(B+1)-1まで作れるようになる。
これを繰り返せば重心の子頂点が多い場合倍々ゲームで大きな値まで作成できる。

「1つの木に対し1~Aまでの値を作る」はDFSなどで根頂点からの距離が1~Aとなるように割り当てていけばいい。

int N;
vector<int> E[1010];
int num[1010];
int U[1010],V[1010],W[1010];
int A[1010][1010];
int C[1010];

int from[3010];
int D[1010],step[2],nex[2];

pair<int,int> dfs_center(int cur,int pre) {
	pair<int,int> res=make_pair(1<<30,-1);
	int ma=0;
	num[cur]=1;
	
	FORR(r,E[cur]) if(r!=pre) {
		res=min(res,dfs_center(r,cur));
		ma=max(ma,num[r]);
		num[cur]+=num[r];
	}
	return min(res,make_pair(max(ma,N-num[cur]),cur));
}

int dfs(int cur,int pre) {
	C[cur]=1;
	FORR(e,E[cur]) if(e!=pre) C[cur]+=dfs(e,cur);
	return C[cur];
}

void dfs2(int cur,int pre,int id) {
	if(pre!=-1) {
		nex[id]+=step[id];
		D[cur]=nex[id];
		W[A[pre][cur]]=D[cur]-D[pre];
	}
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur,id);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(V);
	FOR(i,N-1) {
		cin>>U[i]>>V[i];
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
		A[U[i]][V[i]]=A[V[i]][U[i]]=i;
	}
	pair<int,int> p=dfs_center(1,-1);
	int c=p.second;
	dfs(c,-1);
	MINUS(from);
	from[0]=0;
	FORR(v,E[c]) {
		for(i=2000;i>=0;i--) if(from[i]!=-1 && from[i+C[v]]==-1) from[i+C[v]]=v;
	}
	
	vector<int> A;
	int a;
	FOR(i,2*N) if(i>=(N+1)/3 && (N-i-1)>=(N+1)/3 && from[i]>=0) {
		int cur=i;
		a=i;
		while(cur) {
			A.push_back(from[cur]);
			cur-=C[from[cur]];
		}
		break;
	}
	step[0]=1;
	step[1]=a+1;
	FORR(a,E[c]) dfs2(a,c,1^count(ALL(A),a));
	
	
	
	FOR(i,N-1) cout<<U[i]<<" "<<V[i]<<" "<<W[i]<<endl;
	
}

まとめ

考え方は単純だけど結構記述量多いな。