省流：\(45+20+5+0=70\)
简称：唐诗
在此膜拜 \(klz\) \(Heldivis\) \(Sorato\) \(czl\) \(Ech0\_7\) yxans lihe_qwq 大佬
T1
先看的 T1 ，想了一个拓排（其实是看错题了），然后过了第一个样例，然后咋调都过不去，就去码暴力了。
过了大概 10min 发现看错题了，然后一会就想出来个 \(O(n^2)\) 的树形 DP （\(45pts\)）然后就润了。
核心代码：
if(x==root) f[x]=g[x];
else
{
f[x]=f[fa[x]]-(siz[x]>=k)+g[x];
ans=max(ans,f[x]);
}
然后正解是钦定一个点为 \(LCA\) 然后 DP （其实赛时想到了但是不会转移，还是 \(\large 菜\)）
核心代码：
void dfs(int x,int fat)
{
siz[x]=1,g[x]=0,f[x]=-1e18;
for(auto y:e[x])
{
if(y==fat) continue;
dfs(y,x);siz[x]+=siz[y];
if(siz[y]>=k) g[x]++;
}
}
void DP(int x,int fat)
{
int mx=-1e18;
for(auto y:e[x])
{
if(y==fat) continue;
DP(y,x);
f[x]=max(f[x],f[y]+g[x]-(siz[y]>=k));
ans=max(ans,mx+f[y]+(n-siz[x]>=k)-(siz[y]>=k));
mx=max(mx,f[y]+g[x]-(siz[y]>=k));
}
ans=max(ans,f[x]+(n-siz[x]>=k));
f[x]=max(f[x],g[x]);
}
T2
首先写的暴力（代码就不放了）（\(10pts\)）
然后 \(L=R=\frac{n\cdot(n+1)}{2}\) 是单调栈板子（\(10pts\)）
正解是二分（但是二分函数不是太好想（就很妙））
核心代码：
inline bool check(int x)
{
int sum=0;
fd(i,1,n) fd(j,1,st[i])
sum+=max(min(x/a[i],j+en[i]-1)-j+1,0ll);
return sum<L;
}
然后堆维护输出就行了
T3
一眼 DP 结果发现是容斥
然后写了个暴力（\(5pts\)）
正解好像是个环
正解还没写完，以后补……
T4
第一眼想到预处理出一个点可控制的区间，然后好像有甚么人类智慧，然后就不会了
然后码了 100+ 行的暴力还没码完……
正解 也是 还没写完，以后补……
总结
真的很糖 完美继承了小奶龙の好习惯
然后很遗憾的是 T1 已经十分接近 \(Accept\) 了，还有 T1 的另外 \(30pts\) 部分分没想到去码（尤其是链那个）……
\(\LARGE 唐\)
