Submission #3386454

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
vector<tuple<int,long,int,int>> G[100000];
long S[100000];
int child[100000];
long ans[99999];
long sumcost[100000];
void Calc(){
	int N = rei();
	for(int i=0;i<N-1;i++){
		int a = rei()-1;
		int b = rei()-1;
		G[a].push_back({b,0,i,G[b].size()});
		G[b].push_back({a,0,i,G[a].size()-1});
	}
	for(int i=0;i<N;i++){
		S[i] = rel();
	}
	stack<pair<int,int>> sp;
	sp.push({0,-1});
	while(!sp.empty()){
		int v = sp.top().first;
		int f = sp.top().second;
		sp.pop();
		if(v >= N){
			v -= N;
			child[v] = 1;
			for(int i=0;i<G[v].size();i++){
				int t = get<0>(G[v][i]);
				if(t != f){
					child[v] += child[t];
				}
			}
		}
		else{
			sp.push({v+N,f});
			for(int i=0;i<G[v].size();i++){
				int t = get<0>(G[v][i]);
				if(t != f){
					sp.push({t,v});
				}
			}
		}
	}
	int halfchild1 = -1;
	int halfchild2 = -1;
	int halfedge = -1;
	stack<tuple<int,int,int>> sp2;
	sp2.push({0,-1,-1});
	while(!sp2.empty()){
		int v = get<0>(sp2.top());
		int f = get<1>(sp2.top());
		int fe = get<2>(sp2.top());
		sp2.pop();
		if(f != -1){
			if(child[v]*2 == N){
				halfchild1 = f;
				halfchild2 = v;
				halfedge = get<2>(G[f][fe]);
			}
			else{
				long cost = (S[v] - S[f]) / (N - child[v]*2);
				ans[get<2>(G[f][fe])] = cost;
				G[f][fe] = {get<0>(G[f][fe]),cost,get<2>(G[f][fe]),get<3>(G[f][fe])};
				int fe2 = get<3>(G[f][fe]);
				G[v][fe2] = {get<0>(G[v][fe2]),cost,get<2>(G[v][fe2]),get<3>(G[v][fe2])};
			}
		}
		for(int i=0;i<G[v].size();i++){
			int t = get<0>(G[v][i]);
			if(t != f){
				sp2.push({t,v,i});
			}
		}
	}
	if(halfchild1 != -1){
		sp.push({halfchild1,-1});
		while(!sp.empty()){
			int v = sp.top().first;
			int f = sp.top().second;
			sp.pop();
			if(v >= N){
				v -= N;
				for(int i=0;i<G[v].size();i++){
					int t = get<0>(G[v][i]);
					if(t != f){
						sumcost[v] += sumcost[t] + get<1>(G[v][i]);
					}
				}
			}
			else{
				sp.push({v+N,f});
				for(int i=0;i<G[v].size();i++){
					int t = get<0>(G[v][i]);
					if(t != f){
						sp.push({t,v});
					}
				}
			}
		}
		ans[halfedge] = (S[halfchild1]-sumcost[halfchild1]) / (child[halfchild1] - 1);
	}
	for(int i=0;i<N-1;i++){
		cout << ans[i] << endl;
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Submission Info

Judge Result