USACO美国信息学奥赛赛事资讯-USACO竞赛最新信息

USACO 竞赛打到哪个级别对申请美本计算机有帮助？零基础备考难度大吗？

在美本申请（尤其是竞争惨烈的 Computer Science，计算机科学专业）中，背景提升的赛道日益拥挤。传统的 AP 成绩和校内 GPA 已经很难让招生官眼前一亮。

作为美国官方最具公信力的中学生计算机赛事，USACO（美国计算机奥林匹克竞赛）近年来成为了无数“代码学霸”申藤、冲刺 Top 30 的核心武器。那么，USACO 到底要打到哪个级别才能在申请中发挥作用？对于毫无编程基础的同学来说，这条路到底有多难？

一、 USACO 级别划分与美本申请的“含金量对照表”

USACO 采取逐级晋级制，所有参赛者首次注册都从铜级（Bronze）开始，在规定时间内达到分数线（或拿满分）即可升入下一级别。级别不同，在名校招生官眼中的分量天差地别：

竞赛级别	对应人群/技术含金量	美本申请实际帮助（以 CS 专业为例）
铜级 (Bronze)	考查基本编程语法、循环逻辑和简单的枚举暴力搜索。	申请无实质帮助：仅能作为课外兴趣的起点，不建议写进学术荣誉栏。
银级 (Silver)	引入基础算法（递归、二分查找、基础图论、贪心算法等）。	Top 30-50 的有效素材：证明你具备基本的计算思维。若冲刺 Top 30，可作为 5 个主要奖项中的“填舱”奖。
金级 (Gold)	涉及高级算法（动态规划 DP、线段树、高阶图论、并查集等）。	顶尖名校的“强力敲门砖”：达到金级意味着你已经进入全球参赛者的前 10%–15%。对于 Carnegie Mellon (CMU)、UC Berkeley、Cornell 等 CS 大牛校，金级是极具说服力的学术硬核证明。
白金级 (Platinum)	纯粹的天才博弈，考查复杂的复合算法与极强的代码调试（Debugging）耐力。	藤校与顶尖理工校的“终极通行证”：迈入白金级（全国前 100-150 人左右），意味着你一只脚已经踩进了 MIT、Caltech 或 Stanford。这相当于体育特长生里的“国家队”级别。

核心结论：

如果你的目标是美本 Top 30 院校的 CS 相关专业，金级（Gold）是具有实质性推动力的起步线；如果能冲击到白金级（Platinum），你的学术背景将在理工科申请中处于金字塔尖。

二、零基础备考，难度到底大不大？

很多同学和家长一听到“奥林匹克”四个字就望而却步。实际上，USACO 的难度呈现“前宽后窄、陡峭上升”的特征。

1.语言关与入门期：对零基础非常友好

USACO 支持 C++、Java、Python 等多种语言。

难度评估：低。

对于零基础（哪怕连一行代码都没写过）的同学，选择 Python 或 C++ 入门，通常只需要 1-2 个月的系统学习，就能完全掌握变量、循环、数组等基础语法，具备冲刺铜级的实力。

2.铜升银、银升金：逻辑与算法的第一个“分水岭”

从银级开始，比赛不再考查“你会不会写代码”，而是考查“你的代码聪不聪明”。

难度评估：中等偏高。

很多校内数学很好的同学在这里会遇到瓶颈。因为校内数学侧重公式推导，而计算机算法要求你把思维转化为“空间复杂度”与“时间复杂度”的最优解。比如，同样一个问题，暴力枚举需要运行几小时，而用二分查找只需要几毫秒。这个转轨期需要大量的刷题（通常需要精刷 50-100 道真题）来建立算法直觉。

3.金升白金：对意志力与天赋的极端考验

难度评估：极高。

这个阶段的题目通常长达数页，各种边界条件错综复杂。不仅要求算法完全正确，还极度考验抗压能力和调试代码的耐心。

三、零基础冲刺金级的“黄金备考路线图”

既然零基础完全可行，那么如何用最短的时间、最科学的路径少走弯路？建议采取以下三个阶段的长线规划：

1.语言筑基与代码规范：第 1-2 个月

选择一门语言（强推荐 C++，因为执行效率最高且在高级算法中模板丰富；或 Python 入门）。彻底吃透条件语句、循环、基本数组操作。在这个阶段，目标是做到“能把自己的逻辑无误地翻译成代码”。

2.铜级破局与算法思维启蒙：第 3-5 个月

开始接触基础算法：暴力枚举、基础排序、模拟题（Simulation）。这个阶段不要盲目刷难题，重点是去官方题库（USACO Guide）完成 Bronze 级别的分类练习，做到一次性快速晋级银级。

3.银级深挖与金级冲刺（核心攻坚期）：第 6-10 个月

全面攻克银级核心：前缀和（Prefix Sums）、双指针、基本图论（DFS/BFS深度与广度优先搜索）、二分查找。每周保持至少 3-5 道真题的敲码量。学会用纸和笔先画出算法流程图，再去写代码。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

USACO各级别核心考点汇总！零基础VS有基础考生备赛策略有何不同？

USACO（USA Computing Olympiad）是面向全球中学生开放的国际顶尖计算机竞赛，无国籍和地域限制，全程线上参赛。赛事分为四个难度递增的级别：青铜级（Bronze）、白银级（Silver）、黄金级（Gold）和铂金级（Platinum），选手需逐级晋级。

一、 USACO各级别核心考点

不同级别的考察重点差异显著，整体呈现从基础语法到复杂算法优化的进阶趋势：

青铜级（Bronze）： 侧重竞赛基础知识、简单的编程语法以及基本的问题解决能力。掌握一门编程语言的基础概念即可应对。

白银级（Silver）： 要求具备一定的算法基础和抽象思维。核心考点包括贪心算法、递归搜索等，并需要了解栈、队列、哈希表等基础数据结构。

黄金级（Gold）： 考察深入的算法知识及最优解的设计。涉及高级数据结构（如线段树、平衡树）、动态规划、图论高级结构（如最短路径、网络流）以及数论进阶等。

铂金级（Platinum）： 难度极高，全面考察复杂的计算机思维。涵盖计算几何、可持久化数据结构、复杂DP优化等尖端话题，要求选手具备灵活解题与代码性能优化的能力。

二、零基础学生备考策略

对于没有编程经验的学生，建议按以下四个阶段循序渐进：

打好语法基础，冲刺青铜：

深耕Python或C++（推荐C++）基础语法，吃透输入输出、循环、数组、字符串等核心概念。配套刷历年真题熟悉出题风格，不盲目攻克难题，先稳住基础题的正确率。

算法入门，冲击白银：

语法扎实后切入基础算法模块，重点学习贪心思想、简单递归与模拟算法。集中练习白银高频经典题型，学会一题多解，总结同类题目的解题模板。

强化高级算法，跨越黄金：

系统学习图论、动态规划、基础搜索等核心算法，搭建完整的知识框架。分模块专项刷题并及时复盘错题，补齐薄弱知识点，提升代码熟练度与解题思维。

高阶拔高，冲刺铂金：

专攻铂金重难点内容（如线段树、网络流、复杂DP优化）。通过定期的高强度模拟实战训练，把控考试节奏，打磨解题思路并优化代码效率，逐步向顶尖段位迈进。

三、有基础学生备考策略

如果已掌握编程语言或参加过其他信息学竞赛，可以更快速地适应USACO的节奏：

精准定位与真题演练： 根据个人实际水平选择合适难度进行练习。建议快速刷近几年的真题，分析官方题解，总结常见题型与考点分布，了解USACO特有的出题风格。

查漏补缺与定向突破： 详细了解每个问题的知识点情况，排查自身的知识盲区。针对薄弱环节（如动态规划状态设计、图论模型构建）进行有针对性的专项学习。

挑战高阶难题： 对于经验丰富的编程者，应主动选择更具挑战性的问题。注重时间复杂度分析和代码鲁棒性，这将有助于进一步提高解决复杂问题的算法能力和编程技能。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

USACO四大级别核心考点拆解！USACO适合哪些学生？何时参赛冲奖机会最大？

随着人工智能的普及，USACO（美国计算机奥林匹克竞赛）已成为全球顶尖理工科学生证明学术实力的“硬通货”。它不仅是申请海外名校CS专业的王牌背景，更是锻炼底层逻辑思维的最佳途径。掌握科学的备考重点与时间规划，是高效冲奖的关键。

一、 USACO四大级别核心考点拆解

USACO的难度呈阶梯式上升，每个级别的考察侧重点截然不同，选手需进行针对性突破：

1.青铜级（Bronze）：夯实基本功与模拟能力

核心定位：无复杂算法，主要考验编程基础与逻辑实现。

备考重点：熟练掌握文件输入输出（I/O）、暴力枚举与双层循环、全程模拟题、基础字符串处理、简单贪心策略以及边界条件判断。

2.白银级（Silver）：算法入门的分水岭

核心定位：从“能写代码”向“懂算法”转变，强调模板熟练度。

备考重点：自定义排序、二分查找与二分答案、区间类贪心、DFS/BFS基础搜索、邻接表存图与简单图论、前缀和与差分、双指针与滑动窗口、栈和队列的基础应用。

3.黄金级（Gold）：难度升级，算法组合与优化

核心定位：正式步入高阶竞赛门槛，要求极强的代码能力与算法组合思维。

备考重点：动态规划（背包、线性、区间、状压基础）、图论进阶（最短路、拓扑排序、最小生成树）、并查集、二分+贪心组合题、记忆化搜索与剪枝、树的遍历与树型DP入门、单调栈/队列与优先队列。

4.铂金级（Platinum）：顶尖水平，思维转化与高级算法

核心定位：国际赛事级别，侧重复杂问题的抽象建模与前沿算法运用。

备考重点：高级DP（斜率优化、数位DP等）、高级图论（强连通分量、2-SAT、网络流基础）、高级数据结构（线段树、树状数组、莫队算法）、数论与组合数学、分治思想与贪心优化。

二、 USACO适合哪些学生？

学习编程不仅是为了成为程序员，更是为了掌握未来社会必备的“人机沟通”工具。以下四类学生在USACO中能获得最大收益：

有基础的初高中生：已具备Python/C++基础，希望拔高竞赛实力，冲击银、金级别奖项以丰富履历。

规划留学的学生：意向申请美本/英本的CS、AI、数学、软件工程等专业，用高等级成绩拉开申请差异化优势。

备战国内信奥的学生：计划参加CSP-J/S、NOIP等赛事，通过USACO实现国内外竞赛双赛道同步提升。

强化逻辑思维的学生：希望通过编程锻炼推理与问题拆解能力，反哺数学、物理等理科学习。

三、何时参赛冲奖机会最大？

1.最佳参赛年级路径：

9年级：稳冲青铜→白银，打牢算法基础。

10年级：主攻白银→黄金，建立核心申请优势。

11年级：冲刺黄金→铂金，完美匹配大学申请季。

2.赛季冲奖黄金窗口：

12月首场月赛：通常难度最友好，新手晋级率最高，应优先拿下首个级别。

1-2月连续两场：节奏紧凑，适合集中突破，快速升银或升金。
(注：9-11年级全力备赛，抓住12月首战破局，是性价比最高的选择。)

四、高效备赛建议

如果你的目标是计算机/CS相关专业，从现在到新赛季开赛，不要盲目刷题。建议优先夯实语言基础（强烈推荐C++），吃透对应级别的核心算法模板，配合历年真题进行限时训练。这不仅能帮你顺利冲奖，更能为未来的文书撰写、大学面试及专业课学习打下坚实基础。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

USACO不同等级对标国内什么水平？不同基础的备赛策略是怎样的？

作为全球认可度极高的信息学竞赛，USACO（美国计算机奥林匹克竞赛）不仅是检验学生算法能力的试金石，更是冲刺海外顶尖名校CS专业的“硬核通行证”。其科学的分级体系和明确的考察重点，为不同基础的学生提供了清晰的成长路径。

一、 USACO等级划分与核心考点

USACO共设四个级别，难度逐级递增，能力要求分层清晰，全面适配不同阶段学生的成长需求：

1.青铜级（Bronze）：编程思维的起点

难度对标：国内CSP-J入门组。

考察内容：主要考察编程基础语法、枚举、模拟及基础逻辑思维。

申请价值：零基础友好，初一学生经过1-2个月学习即可参赛，整体晋级率较高，是培养编程兴趣的最佳起点。

2.白银级（Silver）：算法能力的分水岭

难度对标：国内CSP-S提高组中低难度。

考察内容：引入基础数据结构与效率考量，核心考察贪心算法、DFS/BFS深度广度搜索、前缀和、二分查找等。

申请价值：适合具备一定编程基础的学生，标志着选手从单纯的代码实现向真正的算法设计迈进。

3.黄金级（Gold）：美本申请的“王牌标配”

难度对标：国内NOIP提高组高难度。

考察内容：重难点知识集中爆发，重点考察动态规划（DP）、图论、最短路算法及高级数据结构。

申请价值：这是理工科名校申请的核心加分项。对于志在冲击TOP30美本计算机专业的学生而言，黄金级几乎是“标配”级别的学术背书。

4.铂金级（Platinum）：顶尖名校的“终极敲门砖”

难度对标：国内NOI全国决赛水准。

考察内容：贴近国际赛事难度，侧重高阶算法设计、复杂问题拆解、综合逻辑应用以及多种复合算法的融合。

申请价值：代表高中生在算法领域的顶尖水平，是冲刺藤校CS专业、入选国际集训队的重磅履历，获得该级别奖项在申请世界各大名校时具有极大的录取优势。

二、不同基础学生的差异化备赛策略

针对不同起点的学生，USACO的备赛需要采取截然不同的战术规划：

1.零基础学生：稳扎稳打，夯实底层逻辑

语言选择：赛前需熟练掌握一门编程语言（推荐Python、C++或Java）。

核心任务：系统学习变量、数据类型、控制结构（循环、条件）、函数及文件输入/输出等基本概念，建立严谨的编程思维。

2.有基础选手：精准定位，突破算法瓶颈

备战思路：根据自身水平直接匹配对应级别的题库进行高强度练习。对于经验丰富的编程者，应主动挑战更具难度的题目，以进一步提高算法设计和代码优化的技能。

3.各阶段专项提升建议

青铜升白银：巩固语法基础，熟练掌握初级算法（排序、二分搜索等），通过大量铜级真题将脑海中的想法转化为无Bug的代码。

白银冲黄金：加强对高级算法和数据结构的学习，着重练习银级题库，总结不同类型算法的应用场景，培养对时间复杂度的敏感度。

黄金破铂金：深入精通图论、动态规划等抽象算法。注重代码的极致优化和时间管理，确保在竞赛高压下能高效解决复杂问题。

铂金拔尖：此阶段题目高度开放且复合，建议寻求专业导师的帮助，针对自身薄弱知识点进行排查，制定行之有效的精准提分计划。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

USACO进阶逻辑了解一下！暑期如何弯道超车高效备考USACO？

对于目标申请美本 TOP30 或英本 G5 计算机科学（CS）、人工智能或软件工程专业的同学，USACO（美国计算机奥林匹克竞赛）的奖项是申请背景中不可或缺的“硬通货”。

随着 2026-27 赛季规则的重大调整，USACO 正从单纯的技能竞赛转向“高频度、高时效、高严谨”的学术评估体系。以下是针对新规的解读与暑期备考策略。

一、 2026 赛季USACO三大新规解读：拒绝“侥幸”，强调“时效”

1.认证成绩（Certified Score）强制化：

核心：金级与白金级选手若要晋级或进入训练营，必须在开赛当日（周六）美东时间 12:00-12:15 准时开启比赛。

影响：错过时间窗虽仍可做题，但成绩将失去“认证”资格。这意味着“错峰比赛”或“迟到开赛”将无法获得晋级资格，大家务必在赛前做好时间规划。

2.AI 使用零容忍：

严禁在代码编写与调试环节使用生成式 AI（ChatGPT/Copilot）。这是对真实编程思维的极限施压，代码风格与逻辑的原创性将成为审核重点。

3.等级年度化（时效性背书）：

26-27 赛季起，等级不再是“永久名头”，而是“标注赛季的身份”（如 2026-27 赛季铂金）。这意味着招生官更看重你当下的算法竞争力，而非几年前的历史成绩。

二、 USACO进阶逻辑：从青铜到铂金的跨越

级别	核心难点	晋级关键
青铜 (Bronze)	基础逻辑、简单模拟	克服暴力模拟，建立复杂度分析意识。
白银 (Silver)	图论、二分、前缀和	理解算法底层逻辑，避免对“题型模板”的盲目依赖。
黄金 (Gold)	动态规划(DP)、树形结构、网络流	追求细节处理与复杂场景的综合运用。
铂金 (Platinum)	创新思维、高阶综合	具备与国际顶级竞赛水准接轨的建模能力。

三、暑期备考：针对性进阶路线图

暑假是 USACO 选手的“决胜期”，合理的算法储备是赛季首战告捷的前提。

当前为 Bronze 的选手：

目标：彻底吃透 Silver 核心算法（BFS/DFS、二分、前缀和/差分）。

时间点：力争在 12 月的首轮比赛中，以“降维打击”之势晋级 Silver。

当前为 Silver 的选手：

目标：攻克 Gold 级高级算法（高级 DP、线段树、最短路）。

时间点：争取在 26-27 赛季的 1-2 月场次完成从 Silver 到 Gold 的跨越。

当前为 Gold 的选手：

目标：铂金级储备。

时间点：由于铂金降级制度实施，Gold 组内竞争将愈发激烈，暑期需深度强化算法的实现效率，提前布局铂金赛道。

四、给 CS 申请者的核心建议

代码规范化： 由于 AI 审核严厉，建议从现在起培养良好的编程习惯（如变量命名规范、清晰的注释、模块化编程）。这不仅能规避违规嫌疑，更是专业 CS 学生的基本素养。

拒绝“题海战术”： 很多同学在 Gold 阶段陷入“会做但超时”的陷阱，原因是算法复杂度分析不精准。不要只盯着题量，要对比不同算法的时间/空间复杂度，复盘最优解。

常态化练兵： 如果你在准备 NOIP/NOI，请务必将 USACO 月赛作为算法实战的常态训练，因为 USACO 题目更贴近北美 CS 专业招生官所看重的“工程思维”。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

2025-2026 年 USACO 决赛入围者公布

USACO 很高兴地宣布 2025-2026 赛季的决赛入围者，全部受邀参加 2026 年 USACO 夏季训练营：

除了参加我们训练营并争夺代表美国参加 2026 年国际信息学奥林匹克竞赛的决赛入围者外，以下 EGOI 决赛入围者已受邀参加我们的训练营，其中一些 (*) 还被选为代表美国参加 2026 年欧洲女子信息学奥林匹克竞赛的代表队：

这些计算机科学预科学生因其在 2025-2026 赛季 USACO 比赛中的出色表现而被选中，他们代表了美国最强的算法问题解决者。请与我们一起祝贺这些人所取得的非凡成就！

USACO核心能力要求是什么？USACO高分考场策略看这篇！

美国计算机奥林匹克竞赛（USACO）作为全球含金量极高的算法赛事，不仅考察编程能力，更是一场对逻辑思维与策略规划的综合考验。无论你是刚接触编程的新手，还是志在冲击铂金级的选手，都需要对赛事能力要求与实战技巧有清晰的认知。

一、USACO核心能力要求：从青铜到铂金的进阶之路

USACO的核心在于算法建模能力，即根据题目条件与数据范围，精准分析问题类型、匹配最优算法并建立求解模型。不同组别对能力的要求呈现出明显的阶梯式跨越：

青铜组（Bronze）： 入门级。重点考察基础语法与逻辑思维，掌握基础模拟、贪心算法及简单枚举即可应对。

白银组（Silver）： 进阶级。开始引入算法思维，需掌握基础搜索（DFS/BFS）、简单动态规划（DP）及基础排序算法。

黄金组（Gold）： 高手级。考察深度算法理解，需熟练运用中等难度图论、进阶动态规划、二分查找等常用算法。

铂金组（Platinum）： 顶尖级。接近IOI选拔标准，需掌握网络流、后缀数组、快速傅里叶变换（FFT）、字符串哈希等高级算法与数据结构。

除了算法建模，代码实现与调试能力同样关键。选手需将思路转化为规范、正确的代码，并具备快速排查错误、通过测试点的能力。在语言选择上，熟练掌握C++（尤其是STL标准库）是主流推荐，当然Python和Java也是官方允许的参赛语言。此外，时间管理能力是赛场拿分的保障，如何在4小时内合理分配3道题的思考、编码与调试时间，直接决定了最终得分效率。

二、USACO高分考场策略：拒绝“死磕”，学会取舍

在USACO赛场上，策略往往比单纯的技术更重要。掌握以下实战技巧，能帮你最大化得分：

1.前15分钟：全局评估与选题

切勿一上来就写代码。建议花15分钟快速审阅全部3道题目，结合数据范围推算算法复杂度，明确标注每道题的难度（简单/中等/困难），最终确定最稳妥的解题顺序，避免后期因选题失误而慌乱。

2.科学的时间分配法则

简单题（40-60分钟）：必须全神贯注，确保AC（通过）拿满分。

中等题（80-100分钟）：争取AC，若无法完全解决也要拿到大部分分数。

困难题（60-80分钟）：优先写出暴力解法保底（通常能拿30-50分），有余力再进行优化。

预留30分钟：用于检查代码逻辑、测试边界数据及补充必要注释。

3.关键的“部分分”与“放弃”策略

记住一个黄金法则：3道题各拿40分（总分120），远胜于死磕1道满分而另外两道0分！

何时放弃： 若某题卡壳超过40分钟毫无进展，果断跳过；若已有暴力解法，先提交保底分，再回头优化。

部分分技巧： 面对难题，优先写暴力解法（如O(n³)或O(2ⁿ)），通常n≤20的小数据能轻松通过；或者先处理特殊情况（如n≤100的子任务）。即使算法不完美，只要输出格式正确，往往也能获得5-10分的辛苦分。实战中，每道题至少提交一次，0分和30分的差距是巨大的！

三、USACO新手常见疑问解答

Q1：没有计算机基础能参赛吗？

完全可以！青铜级（Bronze）属于入门难度，并不要求高深的算法背景。通常系统学习1-2个月的Python或C++基础语法就能上手，真题多为简单的逻辑模拟题，非常适合作为编程竞赛的起点。

Q2：中国学生能报名吗？

中国学生可直接报名。 USACO面向全球开放，无国籍限制，中国学生可以直接在官网注册账号，与全球选手同场竞技。

Q3：考这个对中考有用吗？

直接加分有限，但长远价值巨大。虽然USACO成绩在国内中考阶段通常不直接对应加分，但它所锻炼的严密逻辑思维与编程能力，对数学、物理等理科学习有极大的辅助作用。从长远来看，它是未来升学（尤其是申请国内外顶尖理工科院校）极具分量的“隐形助力”和背景提升利器。

【扫码免费领取】USACO真题&高效算法书+USACO一对一辅导规划！

2026 年美国USACO公开赛——最终结果

美国公开赛是我们“全国锦标赛”的赛事。这是一项针对美国预科生的监督邀请赛，参赛者需在前三次月度比赛中表现最优异。

USACO 2026 年美国公开赛

结语

这是我们许久以来首次举办的监考竞赛。这是一次有益的经历，帮助我们为未来的监考竞赛优化细节。总体而言，我认为本次竞赛进行得相当顺利。本次竞赛的结果是我们选拔2026年USACO夏季训练营邀请对象的主要依据之一。

众多人士为本次USACO竞赛的质量与成功作出了贡献，包括Sujay Konda, Bing-Dong Liu, Benjamin Qi, Claire Zhang, Richard Qi, Botao Yuan, Thomas Liu, Avnith Vijayram, Alex Chen, and Brandon Wang。我们还非常感谢本赛季的赞助商——Citadel，感谢他们为我们的项目提供了所有支持！

编码愉快！

2026年USACO公开赛白金奖组问题三—Perfect Binary Trees

**Note: The memory limit for this problem is 512MB, twice the default.**

A perfect binary tree is a rooted tree where every non-leaf node has exactly two children and all leaf nodes are at an equal distance from the root.

An unrooted perfect binary tree is an unrooted tree that is a perfect binary tree when rooted at one of its nodes.

Bessie has a tree with N (1≤N≤10⁵) nodes. Determine the number of ways to remove a subset of edges from the tree so that the resulting forest is a collection of unrooted perfect binary trees. As the answer may be very large, output the result modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains an integer T (1≤T≤100), the number of independent test cases.

The first line of each test case contains an integer N.

Each of the next N−1 lines of each test case contains two integers u_i and v_i (1≤u_i ,v_i≤N) indicating an edge between nodes u_i and v_i .

It is guaranteed that for each test case, the given edges form a tree with N nodes.

Additionally, the sum of N over all test cases does not exceed 2⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a single integer: the number of subsets of edges that, when removed, result in a forest that is a collection of unrooted perfect binary trees, modulo 10⁹+7.

SAMPLE INPUT:

3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 5

SAMPLE OUTPUT:

8
2
14

In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees:

1.(2,6)(2,6)

2.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6)

3.(1,2)(1,2), (2,3)(2,3), (4,6)(4,6)

4.(1,2)(1,2), (2,3)(2,3), (5,6)(5,6)

5.(1,2)(1,2), (4,6)(4,6), (5,6)(5,6)

6.(2,6)(2,6), (4,6)(4,6), (5,6)(5,6)

7.(2,3)(2,3), (4,6)(4,6), (5,6)(5,6)

8.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6), (4,6)(4,6), (5,6)(5,6)

The first subset results in two subtrees of height 11, the last subset results in six subtrees of height 00, and the other subsets result in three subtrees of height 00 and one subtree of height 11.

SCORING:

Inputs 2-3: N≤15
Inputs 4-5: No node is adjacent to more than two other nodes.
Inputs 6-9: N≤1000, the sum of N does not exceed 20002000, and no node is adjacent to more than three other nodes.
Inputs 10-13: No node is adjacent to more than three other nodes.
Inputs 14-21: No additional constraints.

Problem credits: Avnith Vijayram

2026年USACO公开赛白金奖组问题二—Haybale Stacks

**Note: The time limit for this problem is 2.5s.**

Farmer John has N stacks of haybales (1≤N≤5⋅10⁵), where the ith stack contains a_i haybales (1≤a_i ≤10⁹ ). He wants to remove all of these haybales and has M (1≤M≤2500) cows available to help him. If hired, the ith cow will repeat the following s_i times (1≤s_i≤100) for a cost of c_i (1≤c_i≤10⁹):

If the stack contains at least p_i haybales (1≤p_i≤10⁹), then the cow will remove one haybale.

If the stack contains less than p_i haybales, the cow does nothing.

For each stack, FJ wants to remove all of the haybales in it. He will do this by hiring cows in sequence (possibly the same cow more than once) until the stack becomes empty. Help FJ determine for each stack the minimum cost to empty it.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤100), the number of independent tests. Each test is formatted as follows:

The first line contains an integer N. The second line contains N integers,a₁,a₂,…,a_N.

The third line contains an integer M. Then the next M lines will contain p_i,s_i,c_i.

It is guaranteed that the cows will be able to remove all the haybales in every stack. Additionally, it is guaranteed that the sum of N over all tests does not exceed 5⋅10⁵, and the sum of M over all tests does not exceed 2500.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, print N space-separated integers, the ith integer being the cost of removing all the haybales in the ith stack.

SAMPLE INPUT:

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

SAMPLE OUTPUT:

29 155 21
73 328 50

First test: For the last stack of initial size 1010, we can hire cow 33 once, which costs 55 and will remove haybales twice (not thrice because the number of haybales turns to 88 after the second one is removed). Then we can hire cow 22 twice, removing the 88 haybales, resulting in no haybales left. The total cost is 5+8+8=215+8+8=21.

Second test: This satisfies max(s)=1.

SCORING:

Inputs 2-3: a_i≤100
Inputs 4-5: max(s)=1
Inputs 6-9: max(s)≤4
Inputs 10-15: max(s)≤20
Inputs 16-21: No additional constraints.

Problem credits: Sujay Konda