题目描述
在一个 n 个节点（编号为1-n），n 条边的连通图中，每个点的权值都是正整数，每条边的权值为两个端点的权值的和。
已知各边权值，求各点权值。
输入格式
第一行一个整数 n 。
接下来 n 行，每行 3 个整数 x,y,z(1≤x,y≤n)，表示连接点 x 和 y 的边的权值为 z 。
数据保证合法，且没有自环或重边。给出的图中有且只有一个包括奇数个节点的环。
输出格式
$math_inline$n$math_inline$ 行。每行一个正整数 $math_inline$w_i$math_inline$ ，表示点 $math_inline$i$math_inline$ 的权值。
样例输入
3
1 2 3
2 3 5
1 3 4
样例输出
1
2
3
首先我们设第一个点的权值是ans
然后我们以第一个点为起点进行dfs
在dfs的过程中我们可以从中推出一点关于ans的表达式
由于保证有一个环
肯定有一个点出现两个表达式
那么这两个表达式一联立就解得了ans
Code
/**
* author: Akvicor
* created: 2019-07-20 23-14-46
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define prec(x) fixed << setprecision(x)
#define ms(s, n) memset(s, n, sizeof(s))
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD(x) const int MOD = (int)x + 7
#define MAXN(x) const int MAXN = (int)x + 7
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;
/** >------- Akvicor's Solution -------< **/
MOD(1e9);
MAXN(1e6);
int ans;
int vis[MAXN];
PII p[MAXN];
VII ve[MAXN];
void dfs(int x, int fa){
rep(i, sz(ve[x])){
int tmp1 = ve[x][i].fi;
int tmp2 = ve[x][i].se;
if(vis[tmp1] == 1 && tmp1!=fa){
if(p[x].se==1){
ans = (tmp2-p[x].fi - p[tmp1].fi)/2;
}else{
ans = (p[tmp1].fi - tmp2 + p[x].fi)/2;
}
}
if(vis[tmp1] == 0){
vis[tmp1] = 1;
p[tmp1].fi = tmp2 - p[x].fi;
p[tmp1].se = p[x].se^1;
dfs(tmp1, x);
}
}
}
void solve(){
FAST_IO;
ms(vis, 0);
int n, u, v, w;
cin >> n;
loop(i, 1, n){
cin >> u >> v >> w;
ve[u].pb(mp(v, w));
ve[v].pb(mp(u, w));
}
vis[1] = 1;
p[1] = mp(0, 1);
dfs(1, 0);
loop(i, 1, n){
cout << (p[i].second==0 ? p[i].fi-ans : p[i].fi+ans) << endl;
}
}
/** >----------------------------------< **/
int main(){
#ifdef DEBUG
int DEBUGCNT = 0;
clock_t DEBUGstart, DEBUGfinish;
double DEBUGduration;
cout << ">------- Akvicor's Solution -------<" << endl;
DEBUGLOOP:
DEBUGstart = clock();
#endif
solve();
#ifdef DEBUG
DEBUGfinish = clock();
DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
cout << " --> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <--" << endl;
++DEBUGCNT;
if(DEBUGCNT < 100) goto DEBUGLOOP;
cout << ">----------------------------------<" << endl;
#endif
return 0;
}