<\/p>\n
\u94fe\u63a5\uff1aCF<\/a>\/luogu<\/a><\/p>\n Figure Fixing<\/strong><\/p>\n<\/blockquote>\n \u6570\u503c\u4fee\u6b63<\/strong><\/p>\n You have a connected undirected graph made of $n$ nodes and $m$ edges. The $i$-th node has a value $v_i$ and a target value $t_i$.<\/p>\n<\/blockquote>\n \u4f60\u6709\u4e00\u4e2a\u8fde\u901a\u65e0\u5411\u56fe\uff0c\u5b83\u6709 $ n $ \u4e2a\u8282\u70b9\u548c $ m $ \u6761\u8fb9\u3002\u7b2c $ i $ \u4e2a\u8282\u70b9\u6709\u6743\u503c $ v_i $ \u548c\u76ee\u6807\u6743\u503c $ t_i $ .<\/p>\n In an operation, you can choose an edge $(i,j)$ and add $k$ to both $v_i$ and $v_j$, where $k$ can be any integer<\/strong>. In particular, $k$ can be negative.<\/p>\n<\/blockquote>\n \u5728\u4e00\u6b21\u64cd\u4f5c\u4e2d\uff0c\u4f60\u53ef\u4ee5\u9009\u5b9a\u4e00\u6761\u8fb9 $ (i,j) $ \u548c\u4e00\u4e2a\u6574\u6570 $ k $ \uff0c\u7136\u540e\u5c06 $ v_i $ \u548c $ v_j $ \u540c\u65f6\u589e\u52a0 $ k $ . $ k $ \u53ef\u4ee5\u662f\u4efb\u610f\u6574\u6570\uff0c\u7279\u522b\u7684\uff0c$ k $ \u53ef\u4ee5\u662f\u8d1f\u6570\u3002<\/p>\n Your task to determine if it is possible that by doing some finite number of operations (possibly zero), you can achieve for every node $ i $, $ v_i=t_i $.<\/p>\n<\/blockquote>\n \u4f60\u7684\u4efb\u52a1\u662f\u786e\u5b9a\u662f\u5426\u53ef\u80fd\u7528\u6709\u9650\u6b21\u64cd\u4f5c\u4f7f\u5f97\u6240\u6709\u7684\u8282\u70b9\u7684\u6743\u503c\u90fd\u53d8\u4e3a\u76ee\u6807\u6743\u503c\uff0c\u64cd\u4f5c\u6b21\u6570\u53ef\u4ee5\u4e3a $ 0 $ .<\/p>\n \u7b97\u6cd5\uff1a\u4e8c\u5206\u56fe\u67d3\u8272<\/p>\n \u9996\u5148\u6211\u4eec\u53ef\u4ee5\u5c06\u6bcf\u4e2a\u8282\u70b9\u7684\u6743\u503c\u90fd\u5f53\u6210 $ v_i-t_i $ \uff0c\u7136\u540e\u9898\u76ee\u5c31\u8f6c\u5316\u4e3a\u4e86\u5c06\u6bcf\u4e2a\u8282\u70b9\u7684\u6743\u503c\u90fd\u53d8\u4e3a $ 0 $\u200b .<\/p>\n \u53ef\u4ee5\u6ce8\u610f\u5230\uff0c\u6211\u4eec\u7684\u4e00\u6b21\u64cd\u4f5c\u4f1a\u8ba9\u6240\u6709\u7684\u8282\u70b9\u6743\u503c\u548c\u589e\u52a0 $ 2k $ \uff0c\u800c $ 2k $\u200b \u4e00\u5b9a\u662f\u4e00\u4e2a\u5076\u6570\u3002\u4e5f\u5c31\u662f\u8bf4\u5982\u679c\u6240\u6709\u8282\u70b9\u7684\u521d\u59cb\u6743\u503c\u548c\u4e3a\u5947\u6570\uff0c\u90a3\u4e48\u8fd9\u79cd\u60c5\u51b5\u5fc5\u7136\u65e0\u89e3\u3002\u63a5\u4e0b\u6765\u6211\u4eec\u518d\u6765\u8003\u8651\uff0c\u6240\u6709\u8282\u70b9\u7684\u521d\u59cb\u6743\u503c\u548c\u4e3a\u5076\u6570\u7684\u60c5\u51b5\u3002<\/p>\n \u6211\u4eec\u968f\u610f\u9009\u62e9\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u6761\u94fe\u3002<\/p>\n \u5982\u679c\u8fd9\u6761\u94fe\u7684\u957f\u5ea6\u4e3a\u5947\u6570\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u7528\u5982\u56fe\u6240\u793a\u7684\u65b9\u5f0f\u8ba9\u94fe\u7684\u4e24\u7aef\u540c\u65f6\u589e\u52a0 $ k $ .<\/p>\n \u5982\u679c\u8fd9\u6761\u94fe\u7684\u957f\u5ea6\u4e3a\u5076\u6570\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u7528\u5982\u56fe\u6240\u793a\u7684\u65b9\u5f0f\u8ba9\u94fe\u7684\u4e00\u7aef\u589e\u52a0 $ k $ \uff0c\u53e6\u4e00\u7aef\u51cf\u5c11 $ k $ .<\/p>\n \u90a3\u4e48\u4e5f\u5c31\u662f\u8bf4\uff0c\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u8fd9\u4e24\u4e2a\u6027\u8d28\uff0c\u5c06\u5f53\u524d\u8282\u70b9\u7684\u6743\u503c\u201c\u4f20\u9012\u201d\u5230\u5176\u4ed6\u7684\u8282\u70b9\u3002<\/p>\n \u63a5\u4e0b\u6765\u6211\u4eec\u518d\u8003\u8651\u4e00\u4e0b\u73af\u7684\u60c5\u51b5\u3002\u6211\u4eec\u4e0d\u59a8\u8bbe\u73af\u4e0a\u7684\u70b9\u662f $ 1,2,…,n $ \uff0c\u5f53 $ n $ \u4e3a\u5947\u6570\u65f6\uff0c\u53ef\u4ee5\u5c06\u73af\u201c\u62c6\u201d\u4e3a\u4e24\u90e8\u5206\uff0c\u4e00\u90e8\u5206\u662f\u4ec5\u6709\u4e24\u4e2a\u8282\u70b9\u7684\u94fe $ 1,2 $ \uff0c\u53e6\u4e00\u90e8\u5206\u662f $ 2,3,…,n,1 $ \u8fd9\u6761\u94fe\u3002<\/p>\n \u53ef\u4ee5\u6ce8\u610f\u5230\u5728\u7b2c\u4e00\u6761\u94fe\u4e2d $ 1,2 $ \u53ef\u4ee5\u540c\u65f6\u589e\u52a0 $ k $ \uff0c\u800c\u5728\u53e6\u4e00\u6761\u94fe\u4e2d\uff0c$ 1,2 $ \u53ef\u4ee5\u4e00\u4e2a\u589e\u52a0 $ k $ \u53e6\u4e00\u4e2a\u51cf\u5c11 $ k $ \u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u6211\u4eec\u53ef\u4ee5\u5148\u8ba9\u5b83\u4fe9\u540c\u65f6\u52a0 $ k $ \u518d\u8ba9 $ 1 $ \u589e\u52a0 $ 2 $ \u51cf\u5c11 $ k $ \u5c31\u80fd\u5b9e\u73b0 $ 1 $ \u8fd9\u4e2a\u8282\u70b9\u7684\u81ea\u589e\uff08\u53ef\u4ee5\u81ea\u589e\u4efb\u610f\u4e00\u4e2a\u5076\u6570\uff09\u3002\u6240\u4ee5\uff0c\u4efb\u610f\u4e00\u4e2a\u5947\u73af\u4e0a\u7684\u70b9\u90fd\u53ef\u4ee5\u81ea\u589e\u4efb\u610f\u4e00\u4e2a\u5076\u6570\u3002<\/p>\n \u5f53 $ n $ \u4e3a\u5076\u6570\u65f6\uff0c\u73af\u5e76\u6ca1\u6709\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u7684\u7279\u6b8a\u6027\u8d28\u3002<\/p>\n \u7531\u4e8e\u56fe\u91cc\u9762\u7684\u6240\u6709\u8282\u70b9\u7684\u6743\u503c\u548c\u662f\u5076\u6570\uff0c\u90a3\u4e48\u6743\u503c\u4e3a\u5947\u6570\u7684\u8282\u70b9\u4e00\u5b9a\u6709\u5076\u6570\u4e2a\u3002\u6211\u4eec\u5c06\u6743\u503c\u4e3a\u5947\u6570\u7684\u70b9\u4e24\u4e24\u51d1\u4e00\u5bf9\uff0c\u7528\u4e0a\u8ff0\u7684\u201c\u4f20\u9012\u201d\u7684\u65b9\u5f0f\u5c06\u5b83\u4eec\u7684\u6743\u503c\u90fd\u53d8\u6210\u5076\u6570\u3002<\/p>\n \u5982\u679c\u4e00\u4e2a\u56fe\u91cc\u9762\u5b58\u5728\u5947\u73af\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u5c06\u56fe\u4e2d\u5168\u90e8\u8282\u70b9\u7684\u6743\u503c\u90fd\u4f20\u9012\u5230\u5176\u4e2d\u4e00\u4e2a\u5947\u73af\u4e0a\uff0c\u63a5\u7740\u7528\u5947\u73af\u4e0a\u7684\u70b9\u53ef\u4ee5\u81ea\u589e\u7684\u6027\u8d28\u5168\u90e8\u6e05\u96f6\u3002\u4e5f\u5c31\u662f\u8bf4\u5982\u679c\u4e00\u4e2a\u56fe\u5b58\u5728\u5947\u6570\u73af\u5e76\u4e14\u5b83\u7684\u6743\u503c\u548c\u4e3a\u5076\u6570\uff0c\u90a3\u4e48\u5b83\u4e00\u5b9a\u662f\u6709\u89e3\u7684\u3002<\/p>\n \u6211\u4eec\u77e5\u9053\u4e00\u4e2a\u56fe\u662f\u4e8c\u5206\u56fe\u5f53\u4e14\u4ec5\u5f53\u5b83\u6ca1\u6709\u5947\u73af\uff0c\u6211\u4eec\u5df2\u7ecf\u8003\u8651\u4e86\u4e0d\u662f\u4e8c\u5206\u56fe\u7684\u60c5\u51b5\uff0c\u63a5\u4e0b\u6765\u6211\u4eec\u518d\u8003\u8651\u4e00\u4e0b\u4e8c\u5206\u56fe\u7684\u60c5\u51b5\u3002<\/p>\n \u6211\u4eec\u628a\u4e8c\u5206\u56fe\u5212\u5206\u4e3a $ S_1 $ \u548c $ S_2 $ \u4e24\u4e2a\u96c6\u5408\u3002\u7531\u4e8e\u56fe\u662f\u8fde\u901a\u7684\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f $ x \\in S_1,y\\in S_2 $\uff0c\u603b\u5b58\u5728\u4e00\u6761\u4ece $ x $ \u5230 $ y $ \u7684\u8def\u5f84\uff0c\u518d\u7ed3\u5408\u4e8c\u5206\u56fe\u7684\u6027\u8d28\uff0c\u8fd9\u6761\u8def\u5f84\u7684\u957f\u5ea6\u4e00\u5b9a\u662f\u5947\u6570\u3002\u90a3\u4e48\u5982\u679c $ S_1 $ \u5185\u8282\u70b9\u7684\u6743\u503c\u548c\u4e0e $ S_2 $ \u5185\u8282\u70b9\u7684\u6743\u503c\u548c\u76f8\u7b49\uff0c\u6211\u4eec\u901a\u8fc7\u4e0a\u6587\u7684\u6743\u503c\u201c\u4f20\u9012\u201d\u4e00\u5b9a\u53ef\u4ee5\u5c06\u56fe\u7684\u5168\u90e8\u8282\u70b9\u6743\u503c\u6e05\u96f6\uff0c\u5982\u679c\u4e0d\u76f8\u7b49\uff0c\u65e0\u8bba\u6211\u4eec\u600e\u4e48\u201c\u4f20\u9012\u201d\uff0c\u90fd\u4e0d\u53ef\u80fd\u8ba9\u5168\u90e8\u8282\u70b9\u6743\u503c\u6e05\u96f6\u3002<\/p>\n \u5230\u8fd9\u91cc\uff0c\u8fd9\u9053\u9898\u7684\u505a\u6cd5\u5c31\u5f88\u660e\u4e86\u4e86\u3002<\/p>\n \u96be\u5ea6&\u63a8\u8350\u6307\u6570\uff1a \u601d\u7ef4\u96be\u5ea6\uff1a\u63d0\u9ad8+\/\u7701\u9009- \u5b9e\u73b0\u96be\u5ea6\uff1a\u666e\u53ca\/\u63d0\u9ad8- \u63a8\u8350\u6307\u6570\uff1a8.5\uff08\u63a8\u8350\u6307\u6570\u6700\u9ad8\u4e3a1 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[10],"class_list":["post-121","post","type-post","status-publish","format-standard","hentry","category-4","tag-10"],"_links":{"self":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/121","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=121"}],"version-history":[{"count":3,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/121\/revisions"}],"predecessor-version":[{"id":125,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/121\/revisions\/125"}],"wp:attachment":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\u9898\u76ee\u7ffb\u8bd1<\/h2>\n
\n
\n
\n
\n
\u9898\u89e3<\/h2>\n
![\"\"](\"https:\/\/i.loli.net\/2021\/08\/14\/W4nI7fFGiXPDweJ.png\")
<\/div><\/p>\n![\"\"](\"https:\/\/i.loli.net\/2021\/08\/14\/Qn26qhevVP31cHD.png\")
<\/div><\/p>\n#include<stdio.h>\n#define MAXN 200005\n#define MAXM 200005\ntypedef long long ll;\nstruct node{\n int eh;\n int v;\n int c;\n}V[MAXN];\nll s[2];\nstruct edge{\n int next;\n int to;\n}E[MAXM*2];\nint tot;\nvoid add_edge(int from,int to)\n{\n E[++tot]=(edge){V[from].eh,to};\n V[from].eh=tot;\n}\nbool vis[MAXN],flag;\nvoid dfs(int i,int c)\n{\n if(vis[i]&&V[i].c!=c)\n {\n flag=true;\n return;\n }\n if(vis[i]) return;\n V[i].c=c;\n vis[i]=true;\n s[c]+=V[i].v;\n for(int p=V[i].eh;p;p=E[p].next)\n {\n dfs(E[p].to,c^1);\n if(flag) return;\n }\n}\nint main()\n{\n int i,T,n,m,t,x,y;\n ll sum;\n scanf("%d",&T);\n while(T--)\n {\n sum=0;\n tot=0;\n s[0]=s[1]=0;\n flag=false;\n scanf("%d%d",&n,&m);\n for(i=1;i<=n;i++)\n scanf("%d",&V[i].v);\n for(i=1;i<=n;i++)\n {\n scanf("%d",&t);\n V[i].eh=0;\n V[i].v-=t;\n sum+=V[i].v;\n vis[i]=false;\n }\n for(i=1;i<=m;i++)\n {\n scanf("%d%d",&x,&y);\n add_edge(x,y);\n add_edge(y,x);\n }\n if(sum%2!=0)\n {\n printf("NO\\n");\n continue;\n }\n dfs(1,0);\n if(flag||s[0]==s[1]) printf("YES\\n");\n else printf("NO\\n");\n }\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"