problem

洛谷鏈接

注意：保證 $C[v]$ 的奇偶性與頂點 $v$ 的度的奇偶性相同。

solution

先考慮樹的情況。這是個經典問題了，從葉子往上推，對于一個點還差的邊權就有這個點和其父親的邊來補足。最后判斷根是否滿足條件即可。

那么怎么將樹的解法擴展到普通圖上面。

先隨便找個這個圖的生成樹吧，單獨考慮每一條非樹邊，會在生成樹上形成一個環，非奇即偶。

假設非樹邊會產生 $\pm x$ 的影響。畫圖發現：

• 如果形成的是偶環那么環上樹邊交替進行 $\pm x$ 的調整。

  $x$ 在 $lca$ 處就會抵消掉，繼續往上相當于沒產生任何貢獻。

• 如果形成的是奇環同樣交替調整。

  $x$ 在 $lca$ 處會產生兩倍的貢獻，繼續往上傳遞 $\pm 2x$。

這個 $x$ 是由我們自行決定的，所以我們完全可以看根需要多少再定這條非樹邊的邊權。

換言之，只要圖中有奇環，那么一定有解。

因此，對于會形成偶環的非樹邊直接邊權等于零，會形成奇環的非樹邊只需要一條邊權為 根需要邊權除以二，其余同樣邊權為零。

暴力更替那個奇環上的邊權答案即可。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100005 vector < pair < int, int > > G[maxn]; int n, m, s, t, ID; bool vis[maxn], color[maxn]; int c[maxn], w[maxn], dep[maxn], ans[maxn], fa[maxn], fa_id[maxn];void dfs1( int u ) {vis[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].first, id = G[u][i].second;if( ! vis[v] ) {fa[v] = u;fa_id[v] = id;dep[v] = dep[u] + 1;color[v] = color[u] ^ 1;dfs1( v );ans[id] = w[v];//由兒子推父親 當與所有兒子v-son邊權確定時v剩下的就只能通過和父親u的連邊彌補w[u] -= w[v];}else if( dep[v] < dep[u] and color[u] == color[v] ) s = u, t = v, ID = id; //返祖邊找到奇環} }void dfs2( int u ) {vis[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].first, id = G[u][i].second;if( id ^ ID and ! vis[v] ) {dfs2( v );ans[id] = c[v];c[u] -= c[v];}} }signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &c[i] ), w[i] = c[i];for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%lld %lld", &u, &v );G[u].push_back( make_pair( v, i ) );G[v].push_back( make_pair( u, i ) );}dfs1( 1 );if( ! w[1] ) {printf( "YES\n" );for( int i = 1;i <= m;i ++ ) printf( "%lld\n", ans[i] );}else if( s ) {memset( vis, 0, sizeof( vis ) );memset( ans, 0, sizeof( ans ) );dfs2( s ); int x = c[s] >> 1, op = 1;while( s ^ t ) {ans[fa_id[s]] += op * x;op *= -1;s = fa[s];}ans[ID] += op * x;printf( "YES\n" );for( int i = 1;i <= m;i ++ ) printf( "%lld\n", ans[i] );}else printf( "NO\n" );return 0; }

總結

以上是生活随笔為你收集整理的CodeForces 901D Weighting a Tree（结论)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。