无题
查看原帖
无题
116137
嘉然小姐的狗楼主2020/6/16 08:52
// #include "pas.h" start
#include <cstdio>
#include <cstring>

#define program bool
#define var
#define Begin int main() {
#define End }
#define begin {
#define end }
#define For(a, n) for(a; i<=n; i++)
#define procedure void
#define inc(x) (x)++;
#define While while
#define Do
#define div /

#define fillchar(a, val, size) memset(a, val, size)

typedef int longint;
typedef bool boolean;

inline void read(int &x) { scanf("%d", &x); }
inline void read(int &a, int &b, int &c) { scanf("%d %d %d", &a, &b, &c); }
inline void writeln(int x) { printf("%d\n", x); }
// #include "pas.h" end

program cycle;

const longint N = 200000 + 10;

var longint i, j, n, t;
var longint u, v, w;
var longint pre[N], to[N], wdis[N], head[N], wcnt;
var longint val[N];
var boolean vis[N];

procedure addedge(longint u, longint v, longint w) 
begin
	inc(wcnt);
	pre[wcnt] = head[u];
	head[u] = wcnt;
	to[wcnt] = v;
	wdis[wcnt] = w;
end

procedure add2edge(longint u, longint v, longint w)
begin
	addedge(u, v, w);
	addedge(v, u, w);
end

Begin
    read(n);
    For(i = 1, n) begin
    	read(u, v, w);
    	add2edge(u, v, w);
    end
    
    u = 1;
    vis[u] = 1;
    t = 0;
	For(i = 1, n) begin
    	j = head[u];
    	While(vis[to[j]] and (to[j] > 1 or i < n)) Do
    		j = pre[j];
    	t = wdis[j] - t;
    	u = to[j];
    	vis[u] = 1;
    end
    
    fillchar(vis, 0, sizeof(vis));
    val[1] = t div 2;
    vis[1] = 1;
    u = 1;
	For(i = 1, n - 1) begin
    	j = head[u];
    	While(vis[to[j]]) Do
    		j = pre[j];
    	val[to[j]] = wdis[j] - val[u];
    	u = to[j];
    	vis[u] = 1;
    end
    
    For(i = 1, n)
    	writeln(val[i]);
End
2020/6/16 08:52
加载中...