别墅装修排名,贵阳网站seo,外贸网站定制,技术开发包括哪些内容传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一颗nnn个点的图#xff0c;每个点都有一个点权cic_ici#xff0c;要求你给每个边赋一个权值kik_iki#xff0c;要求对于每个点与他相连的边的权值之和等于这个点的点权cic_ici。 n≤1e5,n−1≤…传送门 文章目录题意思路题意
给你一颗nnn个点的图每个点都有一个点权cic_ici要求你给每个边赋一个权值kik_iki要求对于每个点与他相连的边的权值之和等于这个点的点权cic_ici。
n≤1e5,n−1≤m≤1e5,−n≤ci≤nn\le1e5,n-1\le m\le 1e5,-n\le c_i\le nn≤1e5,n−1≤m≤1e5,−n≤ci≤n
思路
考虑这个图是一棵树的时候那么我们从叶子开始向上递推一定能推出来每条边的唯一解检查一下根节点是否合法即可。
考虑一般图的情况我们还是先dfsdfsdfs找出来一棵树让后如果此时根节点已经合法那么显然将其他非树边都置为000即可。如果不合法我们考虑如何操作能使其合法。
想想还有什么条件没有用到他是个图我们只拿出来了一棵树不合法的时候只能通过环来平衡一下。考虑两个点u,vu,vu,v他们之间有一条边构成环假设我们将这个边权值置为xxx这两个点在原树中连向父亲的边边权为y,zy,zy,z加上这个边构成环之后边权变成了y−x,z−xy-x,z-xy−x,z−x继续向上递推手玩一下不难发现是正负交替的所以我们分奇偶环来考虑。
(1)(1)(1)考虑偶环的时候设u,vu,vu,v的lcalcalca为fff由于其是奇环那么两个点到fff的距离的奇偶性不同所以他们最终的符号是相反的也就是在fff处两个分别是x,−xx,-xx,−x所以就抵消了并无贡献。
(2)(2)(2)考虑奇环的时候跟上面一样的分析方法可以发现他们最终的状态是相同的也是2x2x2x再向上也是2x2x2x的变化量所以这个是可以用来修改根节点权值的。
所以通过以上分析根节点如果是奇数一定无解否则就找个奇环来构造一下即可。
最后离天下大谱之我一发过了。
// Problem: D. Weighting a Tree
// Contest: Codeforces - Codeforces Round #453 (Div. 1)
// URL: https://codeforces.com/problemset/problem/901/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
vectorPIIv[N];
LL c[N],ans[N];
int fa[N],depth[N],ff[N];
bool st[N],flagfalse;void dfs1(int u) {st[u]1;for(auto x:v[u]) {if(st[x.X]) continue;depth[x.X]depth[u]1;ff[x.X]u;dfs1(x.X);c[u]-c[x.X];ans[x.Y]c[x.X];fa[x.X]x.Y;}
}void solve(int u,int v,int id) {int opdepth[u]1;if(!op) {ans[id]c[1]/2;int op-1;while(u) {ans[fa[u]]op*c[1]/2;uff[u];op*-1;}op-1;while(v) {ans[fa[v]]op*c[1]/2;vff[v];op*-1;}} else {ans[id]-c[1]/2;int op1;while(u) {ans[fa[u]]op*c[1]/2;uff[u];op*-1;}op1;while(v) {ans[fa[v]]op*c[1]/2;vff[v];op*-1;}}
}void dfs2(int u,int fa) {if(flag) return;st[u]1;for(auto x:v[u]) {if(flag) return;if(x.Xfa) continue;if(st[x.X]) {if((depth[u]depth[x.X])%20) {flagtrue;solve(u,x.X,x.Y);return;}continue;}dfs2(x.X,u);}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in;i) scanf(%lld,c[i]);for(int i1;im;i) {int a,b; scanf(%d%d,a,b);v[a].pb({b,i}); v[b].pb({a,i});}dfs1(1);if(c[1]0) {puts(YES);for(int i1;im;i) printf(%lld\n,ans[i]);puts();return 0;} else if(abs(c[1])1) {puts(NO);return 0;}memset(st,0,sizeof(st));dfs2(1,0);if(flag) {puts(YES);for(int i1;im;i) printf(%lld\n,ans[i]);puts();} else {puts(NO);}return 0;
}
/**/
