orz _ztyqwq, SIGSEGV.
给定 (n) 个点，(m) 条边的无向图，要求你给每个节点赋正权值 (a_i)，使得至少有一个节点有非零权值，且：
其中 ((u_i,v_i)) 是图中的一条边。
题解
虽然题目中没有给定图的连通性，但如果有至少一个连通块构造满足条件，则其余节点赋 (0) 就一定合法。所以下面的讨论假定图连通。
首先，注意到给所有节点赋 (1) 时，条件等价于 (nle m)，即对于所有非树图，都存在一种构造。
考虑树的情况时，发现难以直接构造，考虑几种极端情况，比如：链和菊花图。
链
经过尝试，发现链的情况总是无解。证明：
设存在构造，链上每个点的权值为 (a_i)，则原式变形为：
注意到左边一定为非负数，则不等式成立，即等号取到当且仅当 (a_1=a_2=cdots=a_n=0)，与题目条件矛盾，所以一定无解。
菊花图
考虑有解的边界。
显然，将中间的点权赋较大值，周围的点权取小更优。更极端地，所有叶子节点的点权都应为 (1)。设 (f_n(x)) 为 (n) 个点，中间点点权取 (x) 时，条件中 ( ext{右边}- ext{左边}) 的值。则易得表达式为 (f_n(x)=left(x^2+n-1 ight)-left((n-1)x ight)=x^2-(n-1)x+n-1)。
以 (x) 为主元，则 (f_n(x)) 为关于 (x) 的二次方程。即，(exist x\, f(x)ge 0 Leftrightarrow (n-1)^2-4(n-1)ge 0)，舍去不合法根解得 (nge 5)，即至少有 (4) 个叶子节点时一定有解。
构造也十分简单：中间节点赋 (2)，其余点赋 (1)。易证这样一定是合法的。
如何将菊花图的构造拓展到一般的树呢？考虑如下构造：
- 如果该节点的度 (> 1)，即非叶子节点，赋 (2)；
- 否则，即为叶子节点，赋 (1)。
正确性：设有 (k) 个叶子节点，可得：
即 (kge 4)，这与菊花图的限制是相同的。
特殊情况
上面的分类讨论包括了：
- 叶子数为 (2)，这样的树一定是链；
- 叶子数 (ge 4)。
接下来我们将讨论最困难的一种情况：有 (3) 个叶子的树。
手玩片刻后，可能以为 (3) 个叶子是无解的。但考虑如下构造：
节点 (1) 的点权为 (3)，(2,4,6) 为 (2)，其余为 (1)。注意到此时满足条件。
依旧考虑有解的边界。首先注意到对于所有三个叶子节点的树，一定存在恰好一个度为 (3) 的节点（下文称为「根」），而删去这个节点后，这棵树就分成了三条链。
注意到三条链是互相独立的，所以考虑每条链对答案的贡献。注意这里，包括下文，对答案的定义为题目中式子的 ( ext{右边}- ext{左边})。显然，我们希望答案越大越好。
令 (f(x,l)) 为根的权值为 (x) 时，节点数为 (l) 的链的最大贡献。套用链那段公式，即：
构造 (a) 的差分数组 (b)，即 (b_i=a_i-a_{i+1})（为了方便，令 (a_{l+1} = 1)）。则
由于 (sum b_i=x)，则均分一定最小，即：
所以 (f(x,l)=-dfrac{x^2}{2}-dfrac{x^2}{2l})，则答案为：
等价于：
这就是最终的条件。考虑给出构造。注意到我们只需要给出 ({1over l_1}+{1over l_2}+{1over l_3}= 1) 的构造即可（可证如果有构造，则答案一定恰好为 (0)），其余的情况中，一定存在删去某些链的末端得到上述情况的方法。此时只需要将该删去的节点赋成上一个（距离根更近的）的值，易证这样对答案无影响。
通过枚举，发现只有 ((3,3,3))，((2,4,4))，((2,3,6)) 满足条件。同时，要使答案恰好为 (0)，则上述所有不等式均须取到等号，即要满足 (b_i) 全部相等。考虑如下构造：
- 根节点权值为 (l_1l_2l_3)；
- 以第一条链为例，如果距离根节点距离为 (x)，则权值为 ((l_1-x)l_2l_3)。
容易证明这样的构造是满足条件的。
最后，总结一下整体的步骤：
- 提取连通块；
- 检查是否为树；
- 检查叶子节点个数；
- 检查链长。
精细实现可以达到 (mathcal{O}(nalpha(n))) 的复杂度。（不太理解 (mathcal{O}(n)) 是什么科技）
注意事项
注意查链时的判重。