This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 1e5 + 10;
const int MAXM = 5e5 + 10;
vector<pii> adj[MAXN];
int bEdge = -1;
vector<pii> edges;
int h[MAXN];
int change[MAXN];
bool vis[MAXN];
int dad[MAXN];
int dp[MAXN];
int peso[MAXM];
void dfs(int node) {
vis[node] = 1;
for (auto [u, z] : adj[node]) {
if (u == dad[node]) continue;
if (vis[u]) bEdge = z;
else {
dad[u] = node;
h[u] = h[node] + 1;
dfs(u);
}
}
}
void calc(int node) {
vis[node] = 1;
for (auto [u, z] : adj[node]) {
if (vis[u]) continue;
calc(u);
dp[node] += (change[u] - dp[u]);
peso[z] += (change[u] - dp[u]);
}
}
vector<int> path;
bool found = 0;
int need;
void cPath(int from, int to) {
path.clear();
while (to != from) {
path.push_back(to);
to = dad[to];
}
path.push_back(from);
reverse(path.begin(), path.end());
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> change[i];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edges.push_back({a, b});
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
if (m > n) {
cout << "0\n";
return 0;
}
dfs(1);
int lca = 0;
if (bEdge != -1) {
auto u = edges[bEdge];
int a = u.fr, b = u.se;
if (h[b] > h[a]) swap(a, b);
lca = b;
int tam = h[a] + h[b] - 2*h[lca] + 1;
if ((tam % 2LL) == 0) {
cout << "0\n";
return 0;
}
}
memset(vis, 0, sizeof vis);
calc(1);
if (dp[1] == change[1]) {
for (int i = 0; i < m; i++) cout << 2*peso[i] << "\n";
return 0;
}
// first case is for tree
// second case is if you can't add 2x to it
if ((bEdge == -1) || ((change[1] - dp[1]) % 2LL)) {
cout << "0\n";
return 0;
}
need = (change[1] - dp[1])/2LL;
cPath(1, lca);
int tam = path.size();
int inv = 1;
for (int i = 0; i < (tam - 1); i++) {
int node = path[i];
int prox = path[i + 1];
for (auto [u, z] : adj[node]) {
if (u == prox) {
peso[z] += 2*need*inv;
inv = -inv;
break;
}
}
}
int a = edges[bEdge].fr, b = edges[bEdge].se;
if (h[b] > h[a]) swap(a, b);
cPath(lca, a);
tam = path.size();
for (int i = 0; i < (tam - 1); i++) {
int node = path[i];
int prox = path[i + 1];
for (auto [u, z] : adj[node]) {
if (u == prox) {
peso[z] += need*inv;
inv = -inv;
break;
}
}
}
if ((h[a] - h[lca]) % 2LL) inv = -inv;
peso[bEdge] += inv*need;
for (int i = 0; i < m; i++) {
cout << peso[i] << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |