P7246 手势密码

  众目睽睽之下被要求解锁另一个人的手机是一件非常恐怖的事。   ——特别是密码关于自己的时候。 ---   被堆在讲台周围乌压压的同学围着，小灰毛表示自己真的很难。作为班长的阿绫被叫去开会，存着月考名次表的手机被交给天依保管。但消息不出意料地走漏，现在一班觊觎着分数数据的饿狼一致要求天依打开手机……   “真不知道密码啊！”拖延着，心里早就猜到手势密码的答案。   最后，试探而肯定地划出一个字母“Y”，解锁成功。什么意思呢？首先排除“依”的首字母。   这个时候肯定有起哄的啦！   “懂的都懂\~”“别问，问就是 [XX即是正义！](https://www.bilibili.com/video/BV1z741137vQ)”……

乐正大小姐用的手机很高级，所以她的手势密码也很花哨。 具体地，现在有一棵 $n$ 个结点的树，对于两个结点 $u,v$，当且仅当 $(u,v)$ 是一条树边时，手势才能从其中一个点（$u$ 或 $v$）划向另一个点（$v$ 或 $u$）。更奇怪的是，这种手势密码不限制仅划一次，但每次划出的路径必须是树上的一条简单路径。 现在阿绫告诉了天依在她的密码中每个结点被手势划过的次数（作为手势的起点或终点也算划过一次），其中第 $i$ 个结点划过 $a_i$ 次。那么，天依至少要划多少次才能解开密码呢？ ---- #### 简化题意 有一棵带点权的树。定义一次操作为选择树上的一条简单路径，并将这条简单路径上的所有点点权减去 $1$。问至少需要多少次操作，使树上所有点的点权**恰好**变为 $0$。

无

无

#### 样例解释 2 给出的树形态如下，括号中的数字表示该点的点权。  一种最优的操作方案为 $(3,4)\times2,(4,5),(4,4)\times4,(5,5)\times4,(4,7),(7,8),(6,7)\times6$。其中 $(u,v)$ 表示对从 $u$ 到 $v$ 的简单路径进行一次操作。 ------------ #### 数据规模与约定 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$op\in\{1,2\}$，$1\le seed\le 10^9$，$1\le n\le 3\times 10^6$，$0\le a_i\le10^9$，$1\le u,v\le n$，保证 $u\ne v$。 | 子任务 | 分值 | $op$ | $n$ | $a_i$ | 特殊性质 | | :----: | :--: | :--------: | :----------------------: | :-------------: | :------: | | 1 | 1 | $1$ | $2$ | / | / | | 2 | 4 | $1$ | $3$ | / | / | | 3 | 10 | $1$ | $\leq 6$ | $\leq 3$ | / | | 4 | 5 | $1$ | $\leq 10^6$ | / | A | | 5 | 15 | $1$ | $\leq 50$ | / | / | | 6 | 5 | $1$ | $\leq 5\times 10^3$ | $\leq 100$ | B | | 7 | 10 | $1$ | $\leq 10^5$ | $\leq 100$ | B | | 8 | 10 | $1$ | $\leq 10^5$ | / | C | | 9 | 10 | $1$ | $\leq 10^5$ | $\leq 100$ | / | | 10 | 30 | / | / | / | / | - 特殊限制 A：对于第 $i$ 条边 $(u,v)$，保证 $u=i,v=i+1$。 - 特殊限制 B：输入的边构成一棵满二叉树。 - 特殊限制 C：对于 $\forall 1\le i\le n$ 有 $a_i=1$。 ------------ #### 提示 Subtask 10 时限 2S。 对于 $op=2$ 的数据，输入的模板只用于减小输入量，标程不依赖该数据生成方式。 【2024.7.2 补充】@[Edward1002001](https://www.luogu.com.cn/user/151415) 指出，Subtask 10 的数据生成器生成的树形并没有随机性。（因为在生成 $2$ 的父亲时，最终 `seed` 一定会变为 $1$，此后的随机序列就完全相同了。）这一点不影响数据的正确性，但导致数据强度下降，我们为此致歉。鉴于本题提交较多，不做题面和数据修改。