关键词：
@description@
为了保护环境，p6pou建设了一个垃圾分类器。
垃圾分类器是一个树形结构，由 n 个垃圾桶和 n-1 条双向传送带组成。
垃圾处理器的编号为 1, 2, ..., n，每条传送带都可以花 1 秒钟将垃圾从一个垃圾桶输送到另一个垃圾桶。
垃圾投放点是编号为 r 的垃圾桶，垃圾总是投放在这里。
垃圾共有 n 种，编号也是 1, 2, ..., n。
编号为 i 的垃圾会被输送到编号为 i 的垃圾桶里面，垃圾总是自动沿着最短路线输送，到达编号为 i 的垃圾桶后需要 ai 秒才能被垃圾桶处理完成。
为了避免不同垃圾混在一起，p6pou将垃圾按照编号从小到大的顺序依次投入编号为 r 的垃圾桶，每投放一种垃圾之后，必须等到这种垃圾被输送到其他垃圾桶，或者被编号为 r 的垃圾桶处理完成，才能继续投放下一种垃圾。
传送带输送垃圾也一样，如果要将垃圾从编号为 x 的垃圾桶中的垃圾传输到编号为 y 的垃圾桶，如果此时编号为 y 的垃圾桶中有另一种垃圾，必须等到另一种垃圾被传输走或者被处理完成后才能传输。
现在p6pou想知道，开始投放垃圾到垃圾分类器处理完所有所有垃圾，总共需要花费多长时间。
输入格式
第一行两个整数 n, r，垃圾种类和垃圾桶数量都是 n，垃圾投放点是编号为 r 的垃圾桶。
第二行 n 个整数 a1, a2, ..., an，表示第 i 个垃圾桶处理第 i 种垃圾的时间。
接下来 n - 1 行每行两个数 x, y，表示有一条双向传送带连接编号为 x, y 的两个垃圾桶。
输出格式
输出一个整数，表示从开始投放垃圾到处理完所有垃圾的总时间。
输入输出样例1
样例输入
3 2
5 2 5
1 2
1 3
样例输出
14
样例说明
开始投放 2 秒后，1 号垃圾到达 1 号垃圾桶，2 号垃圾到达 2 号垃圾桶，3 号垃圾还没投放；
开始投放 4 秒后，2 号垃圾处理完成；
开始投放 5 秒后，3 号垃圾到达 2 号垃圾桶，此时 1 号垃圾桶仍在处理 1 号垃圾，所以 3 号垃圾无法传输， 在此等待；
开始投放 7 秒后，1 号垃圾处理完成；
开始投放 9 秒后，3 号垃圾到达 3 号垃圾桶；
开始投放 14 秒后，3 号垃圾处理完成。此时，所有垃圾都已经处理完。
输入输出样例2
样例输入
6 4
6 5 4 3 2 1
1 2
3 2
2 4
5 4
1 6
样例输出
18
样例说明
开始投放 9 秒后，1 号垃圾处理完；
开始投放 8 秒后，2 号垃圾处理完；
开始投放 14 秒后，3 号垃圾处理完；
开始投放 12 秒后，4 号垃圾处理完；
开始投放 16 秒后，5 号垃圾处理完；
开始投放 18 秒后，6 号垃圾处理完。
数据规模与约定
对于100%的数据， n <= 100000, 0 <= ai <= 10^9, 1 <= x, y <= n。
@solution@
首先转化一下问题，去除投放垃圾这一过程：
我们从 r 开始连出去 n 个点连成一条链，并把 1~n 号垃圾从前往后放置在这些点上面。即 n -> n-1 -> ... -> 1 -> r（前面的 1~n 是垃圾放置的对应结点）。
这样就只剩下垃圾在结点之间移动了。
考虑垃圾之间一般是不会互相影响的，垃圾 x 会堵塞垃圾 y，要么是因为垃圾 x 本身在处理，要么是垃圾 x 被前面某个垃圾间接堵塞了。
我们记标记 (x, t) 表示在时刻 t 之前无法通过 x，而从时刻 t 开始可以通过结点 x（通过包含到达的情况）。
注意这里的标记是一个下界，不一定时刻 t 一定就有垃圾通过结点 x。
那么标记的产生就会两种情况：某垃圾被处理了，某垃圾被间接堵塞了。
对于第 i 个垃圾，它到达的时间受它所在结点与目的地之间的路径上所有标记的影响。
它的终点为点 i，因为这些标记 (x, t) 对于 i 的影响为 t + dep[i] - dep[x]。
我们维护 max(t - dep[x])，就可以快速求出一个点到达目的地的时间。
然后考虑怎么维护标记：
先考虑间接堵塞，我们发现这个等价于所有标记上移到结点的父亲。
如果是在链上，这个操作可以用平衡树来维护（貌似也可以用线段树）。
如果是在树上，最常见的就是树链剖分转为序列问题。但是从重链顶端上移时，需要进行类区间拆分与区间合并的操作。于是就不得不用什么平衡树来做了。
貌似用 lct 要更自然一点。不过 splay 太难写了（
然后是自己被处理，会产生一个 (max(t - dep[x]) + dep[i] + a[i] +1, x) 的标记。平衡树上直接插入即可。这里的插入必须要在标记向上爬之后再插。
当然为了保证合法，我们还要加上标记 (1, 1)。
时间复杂度 O(nlog^2n)。
@accepted code@
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF = (1LL<<60);
const int MAXN = 200000;
struct node
ull pri;
ll tg, mx, val;
int dep;
node *ch[2];
pl[MAXN + 5], *ncnt, *NIL;
typedef pair<node*, node*> Droot;
struct treap
treap()
NIL = ncnt = &pl[0];
NIL->mx = -INF;
NIL->ch[0] = NIL->ch[1] = NIL;
ull get_rand()
ull p = rand(), q = (p << 16) | rand();
ull u = rand(), v = (u << 16) | rand();
return (q << 32) | v;
node *newnode(ll x, int d)
node *p = (++ncnt);
p->dep = d, p->mx = p->val = x;
p->pri = get_rand(), p->tg = 0;
p->ch[0] = p->ch[1] = NIL;
return p;
void maintain(node *x, ll k)
if( x == NIL ) return ;
x->tg += k, x->mx += k, x->val += k, x->dep -= k;
void pushup(node *x)
x->mx = max(max(x->ch[0]->mx, x->ch[1]->mx), x->val);
void pushdown(node *x)
if( x->tg )
maintain(x->ch[0], x->tg);
maintain(x->ch[1], x->tg);
x->tg = 0;
node *merge(node *x, node *y)
if( x == NIL ) return y;
if( y == NIL ) return x;
pushdown(x), pushdown(y);
if( x->pri < y->pri )
x->ch[1] = merge(x->ch[1], y);
pushup(x); return x;
else
y->ch[0] = merge(x, y->ch[0]);
pushup(y); return y;
Droot split(node *x, int k)
if( x == NIL ) return make_pair(NIL, NIL);
pushdown(x);
if( k < x->dep )
Droot p = split(x->ch[0], k);
x->ch[0] = p.second; pushup(x);
return make_pair(p.first, x);
else
Droot p = split(x->ch[1], k);
x->ch[1] = p.first; pushup(x);
return make_pair(x, p.second);
node *insert(node *x, node *y)
Droot p = split(x, y->dep);
return merge(p.first, merge(y, p.second));
T;
struct edge
int to; edge *nxt;
edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v)
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->nxt = adj[v], adj[v] = p;
int hvy[MAXN + 5], siz[MAXN + 5], dep[MAXN + 5], fa[MAXN + 5];
void dfs1(int x, int f)
siz[x] = 1, dep[x] = dep[f] + 1, fa[x] = f, hvy[x] = 0;
for(edge *p=adj[x];p;p=p->nxt)
if( p->to == f ) continue;
dfs1(p->to, x);
siz[x] += siz[p->to];
if( siz[hvy[x]] < siz[p->to] )
hvy[x] = p->to;
node *rt[MAXN + 5];
int top[MAXN + 5], tid[MAXN + 5], dfn[MAXN + 5], dcnt = 0;
void dfs2(int x, int tp)
rt[x] = NIL;
top[x] = tp, tid[x] = (++dcnt), dfn[dcnt] = x;
if( !hvy[x] ) return ;
dfs2(hvy[x], tp);
for(edge *p=adj[x];p;p=p->nxt)
if( p->to != fa[x] && p->to != hvy[x] )
dfs2(p->to, p->to);
void insert(int x, ll k)
node *p = T.newnode(k - dep[x], dep[x]);
rt[top[x]] = T.insert(rt[top[x]], p);
ll query(int x)
ll ret = -INF;
while( x )
Droot p = T.split(rt[top[x]], dep[x]);
ret = max(ret, p.first->mx);
rt[top[x]] = T.merge(p.first, p.second);
x = fa[top[x]];
return ret;
void update(int x)
node *y = NIL;
while( x )
Droot p = T.split(rt[top[x]], dep[x]);
T.maintain(p.first, 1);
rt[top[x]] = T.merge(p.first, p.second);
p = T.split(rt[top[x]], dep[top[x]] - 1);
rt[top[x]] = T.insert(p.second, y), y = p.first;
x = fa[top[x]];
int a[MAXN + 5], n, r;
int main()
freopen("garbage.in", "r", stdin);
freopen("garbage.out", "w", stdout);
srand(0307); scanf("%d%d", &n, &r);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]);
for(int i=1;i<n;i++)
int u, v; scanf("%d%d", &u, &v);
addedge(u, v);
addedge(r, n + 1);
for(int i=2;i<=n;i++) addedge(n + i - 1, n + i);
dfs1(2*n, 0), dfs2(2*n, 2*n), insert(r, 1);
ll ans = 0;
for(int i=1;i<=n;i++)
ll tmp = dep[i] + query(i) + a[i];
update(i), insert(i, tmp + 1);
ans = max(ans, tmp);
printf("%lld
", ans);
@details@
出题人在嘲讽选手是垃圾
话说树链剖分套平衡树是否超出了 CSP 的考纲范围内。
（也不一定，毕竟去年连 ddp 都考）
csp-s模拟19/11/02
将最后形成的三元组分类三个一样的，两个一样的，三个都不一样的分别计算就比较方便三个一样的和两个一样的可以三个都不一样显然枚举两个然后算出另一个关于手写一些可以实现功能的东西可以用一个类似邻接表的东西存... 查看详情
[考试反思]1026csp-s模拟测试89：不公(代码片段)
稍垃圾。因为T1没A。赶巧前一段时间学了杜教筛，结果因为教练放错题。然后考场上疯狂yy，最后水到了一个AC。其实的确挺不公平的，不少人也没学呢。如果只算T1和T3的分数的话，那70分就是个垃圾。还有。。。。又一次盖掉... 查看详情
csp-s模拟19/11/01
求出全局后按题意模拟即可，注意可以和取避免暴的问题#include<bits/stdc++.h>#definecsconstusingnamespacestd;typedeflonglongll;llread()llcnt=0,f=1;
csp-s模拟测试70
发现不码题解还是记不清题。A.木板枚举$y_E$，求出$x_F$关于$y_E$的式子，设$y_E$为$x$，发现$Ans=sumlimits_{x=1}^{n-1}[n|x^2]$考场上受《神炎皇》启发，提出$gcd$，设$gcd(x,n)=d$$n‘d|x‘^2d^2$$n‘|x‘^2d$又因为$gcd(n‘,x‘)=1$所以$gcd(n‘,x‘^2)=1... 查看详情
[csp-s模拟测试63]题解
A.Median这题的数据生成方式并没有什么规律，所以可以认为是随机数据。维护一个桶，表示当前K长区间里的值域情况。并且用变量记录中位数值域上的左侧有多少个数，当区间调整时一并调整桶和这个变量即可。由于是随机数据... 查看详情
[csp-s模拟测试]:神炎皇（数学）
题目描述 神炎皇乌利亚很喜欢数对，他想找到神奇的数对。 对于一个整数对$(a,b)$，若满足$a+bleqslantn$且$a+b$是$ab$的因子，则称为神奇的数对。请问这样的数对共有多少呢？输入格式一行一个整数$n$。输出格式一行一个整... 查看详情
[csp-s模拟测试]:endlessfantasy（dfs）
题目描述中二少年$cenbo$幻想自己统治着$EuphoricField$。由此他开始了$EndlessFantasy$。$EuphoricField$有$n$座城市，$m$个民族。这些城市之间由$n-1$条道路连接形成了以城市$1$为根的有根树。每个城市都是某一民族的聚居地，$cenbo$知道第$... 查看详情
垃圾分类数据集+垃圾分类识别训练代码(pytorch)(代码片段)
垃圾分类数据集+垃圾分类识别训练代码(Pytorch)目录垃圾分类数据集+垃圾分类识别训练代码(Pytorch)1.前言2.垃圾数据集说明（1）垃圾数据集dataset1（2）垃圾数据集dataset23.垃圾分类识别模型训练（1）项... 查看详情
[csp-s模拟测试]:炼金术士的疑惑（模拟+数学+高斯消元）
题目传送门（内部题70）输入格式第一行一个正整数$n$，表示炼金术士已知的热化学方程式数量。接下来$n$行，每行一个炼金术士已知的热化学方程式。最后一行一个炼金术士想要求解的热化学方程式，末尾记为$H=?$。每个热化... 查看详情
[csp-s模拟测试]:beauty（搜索）
题目描述距离产生美。一棵包含$n$个点的树，有$2k$个不同的关键点，我们现在需要将这些点两两配对，对于一种形如：$$(u_1,v_1),(u_2,v_2),...,(u_k,v_k)$$的配对方案，我们定义其美丽值为：$$beauty=sumlimits_{i=1}^kdist(u_i,v_i)$$（其中$dist(u,... 查看详情
“你是什么垃圾？”智能垃圾箱为你解答
“你是什么垃圾？”的确是直击灵魂深处的拷问7月，上海正式推行垃圾分类，46座重点城市也传出消息将在2020年加入战场，一股焦虑情绪迅速蔓延开来。面对居委会大妈灵魂拷问，年轻人买最贵的垃圾桶，熬夜恶补垃圾分类知... 查看详情
[考试反思]1024csp-s模拟测试85：以为(代码片段)
愈发垃圾。T1基本全场切（除了RP<-inf的zkt和把人擦）然后T2想了半天逐渐趋近于正解，但是因为数据有问题锅了25分，没什么好说的。T3连题意转化都没有完成。括号匹配转为+1/-1做法都看过多少次了，还不会。。。一定要吸取... 查看详情
csp-s模拟19/10/30
T1：给定两个长度为的序列你需要选择一个区间，使得且。最大化你选择的区间长度解：枚举右端点，查最小的左端点需要
基于html5+webgl实现的垃圾分类系统
前言垃圾分类，一般是指按一定规定或标准将垃圾分类储存、分类投放和分类搬运，从而转变成公共资源的一系列活动的总称。分类的目的是提高垃圾的资源价值和经济价值，力争物尽其用。垃圾在分类储存阶段属于公众的私有... 查看详情
垃圾分类主题班会ppt模板
...个地球公民的义务，今天分享的是一份来自办公资源网的垃圾分类主题班会PPT模板，模板可用于环境保护，节能减排，再生能源汇报演讲。PPT内容从三方面来陈述：垃圾的处理现状；2.垃圾的分类：垃圾可分为四类，可回收垃圾... 查看详情
android垃圾分类app垃圾分类之图像输入
...、识别相册图片七、识别拍照图片八、垃圾分类九、源码前言 在上一篇文章中完成了语音输入，这一篇来写图像输入正文 图像输入无非就是图片识别嘛，再通俗一点就是识别手机中的照片... 查看详情
环卫车载dvr国产方案—推进垃圾分类利国利民
7月上海正式推行垃圾分类，一石激起千层浪，把垃圾分类推向到了风口浪尖。标志着我国在全国积极推行垃圾分类制度的开展。根据住建部、发改委、生态环境部等九部门联合印发《住房和城乡建设部等部门关于在全国地级及... 查看详情
csp-s模拟19/10/02
CF65AHarryPotterandThreeSpells考察严谨的思维与特判如果那么永远不会有金子在的情况下，如果，那么会有无限多的金子在的情况下，如果那么不会有铅在的情况下，如果那么会有无限多的铅在