1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstdio>
using namespace std;
int n, s[200005], m, hea[200005], cnt, uu[200005], vv[200005];
int fa[200005], sum[200005], dep[200005];
bool vis[200005];
struct Edge{
int too, nxt;
}edge[400005];
int myfind(int x){
return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
void dfs(int x, int f){
sum[x] = s[x];
dep[x] = dep[f] + 1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f){
dfs(t, x);
sum[x] += sum[t];
}
}
}
int main(){
cin>>n;
int orz=0;
for(int i=1; i<=n; i++){
scanf("%d", &s[i]);
orz += s[i];
fa[i] = i;
}
if(orz){
printf("Impossible\n");
return 0;
}
cin>>m;
for(int i=1; i<=m; i++){
scanf("%d %d", &uu[i], &vv[i]);
int p=myfind(uu[i]), q=myfind(vv[i]);
if(p!=q){
vis[i] = true;
add_edge(uu[i], vv[i]);
add_edge(vv[i], uu[i]);
fa[q] = p;
}
}
dfs(1, 0);
printf("Possible\n");
for(int i=1; i<=m; i++){
if(!vis[i]) printf("0\n");
else if(dep[uu[i]]<dep[vv[i]]) printf("%d\n", sum[vv[i]]);
else printf("%d\n", -sum[uu[i]]);
}
return 0;
}
|