题目链接

AtCoder：https://agc010.contest.atcoder.jp/tasks/agc010_c

洛谷：https://www.luogu.org/problemnew/show/AT2304

Solution

窝yy了好久的dpQAQ

标算很巧妙：我们考虑算每条边被经过了多少次，这里把一个叶子节点到另一个叶子节点的取石子看成\(\rm travel\)。

首先选一个度数大于一的点作为根节点，然后我们分类讨论：

• 每个叶子节点上面的边\(cnt\)一定等于当前点的石子数。
• 非叶子节点上面的边可以这样算：因为每个非叶子节点的进入的次数等于出去的次数，并且这个点被取完了，也就是说\(\sum _{v\in edge_x} cnt_v=2v[x]\)，那么我们就可以确定了。

算完这个之后就可以判无解了：

• 如果根节点不满足\(\sum cnt =2v[x]\)就无解。
• 如果某条边的\(cnt\)为负就无解。
• 如果某条边的\(cnt\)大于两端的\(v[x]\)的任意一个就无解。

#include
using namespace std;void read(int &x) {x=0;int f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}void print(int x) {if(x<0) putchar('-'),x=-x;if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf double
#define ll long long
#define end puts("NO"),exit(0)const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;int head[maxn],tot=1,cnt[maxn<<1],n,v[maxn],d[maxn],rt;
struct edge{int to,nxt;}e[maxn<<1];void add(int u,int vv) {e[++tot]=(edge){vv,head[u]},head[u]=tot,d[vv]++;}
void ins(int u,int vv) {add(u,vv),add(vv,u);}void dfs(int x,int fa) {if(d[x]==1) return cnt[head[x]]=cnt[head[x]^1]=v[x],void();int rm=v[x]<<1,t=0;for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=fa) dfs(e[i].to,x),rm-=cnt[i],cnt[i]>v[x]?end,0:0;else t=i;if(!t) return ;if(rm>v[x]||rm<0) end;cnt[t]=cnt[t^1]=rm;
}int main() {read(n);for(int i=1;i<=n;i++) read(v[i]);if(n==2) puts(v[1]==v[2]?"YES":"NO"),exit(0);for(int i=1,x,y;i