代做网站app,巩义seo,中国外协加工网最新订单,软件工程就业方向及薪资待遇problem
洛谷链接
注意#xff1a;保证 C[v]C[v]C[v] 的奇偶性与顶点 vvv 的度的奇偶性相同。
solution
先考虑树的情况。这是个经典问题了#xff0c;从叶子往上推#xff0c;对于一个点还差的边权就有这个点和其父亲的边来补足。最后判断根是否满足条件即可。
那么怎…problem
洛谷链接
注意保证 C[v]C[v]C[v] 的奇偶性与顶点 vvv 的度的奇偶性相同。
solution
先考虑树的情况。这是个经典问题了从叶子往上推对于一个点还差的边权就有这个点和其父亲的边来补足。最后判断根是否满足条件即可。
那么怎么将树的解法扩展到普通图上面。
先随便找个这个图的生成树吧单独考虑每一条非树边会在生成树上形成一个环非奇即偶。
假设非树边会产生 ±x±x±x 的影响。画图发现 如果形成的是偶环那么环上树边交替进行 ±x±x±x 的调整。 xxx 在 lcalcalca 处就会抵消掉继续往上相当于没产生任何贡献。 如果形成的是奇环同样交替调整。 xxx 在 lcalcalca 处会产生两倍的贡献继续往上传递 ±2x±2x±2x。 这个 xxx 是由我们自行决定的所以我们完全可以看根需要多少再定这条非树边的边权。
换言之只要图中有奇环那么一定有解。
因此对于会形成偶环的非树边直接边权等于零会形成奇环的非树边只需要一条边权为 根需要边权除以二其余同样边权为零。
暴力更替那个奇环上的边权答案即可。
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;
}
