没去想最优解，无脑树剖。
看到大纲里有就去学了下，不过没过几天现在好像忘了。
组合数学能力还是很差，自己没推出式子来。
离散化完拿树状数组乱搞。
挺妙的感觉，考场上的时候没做出来。
挺一眼的，不过细节有点难调。
一开始当二维数点去做，没调出来换了种做法。
复习强连通分量。
显然对于一个环所有点都能到，缩点后如果出度为 \(0\) 的只有一个就是答案。
缩点完拓扑排序+最长路计数。
建图挺妙的，想不到。
挺板的，答案也比较好观察出来。
了解了下bitset。
写的暴力dp
\(dp[i][j] = max(dp[j][k]) + w[i]\)
计 \(lst_i\) 为 \(a_i\) 上一次出现的位置，查询区间 \([l, r]\) 变为查询满足 \(l \leq i \leq r , 1 \leq lst_i \leq l - 1\) 的个数。
每个 \(k\) 跑一遍单调队列。
先跑行的单调队列存入新数组，新数组再跑一边。
每个点搜完后看看有没有自己能开灯的点可以拓展。
也是记录 \(lst_i\)，对于区间 \([l, r]\) 必须满足有 \(l \leq lst_i\)。线段树和st表都行。
换根dp。
不妨钦定 \(1\) 为根
\(dp1_u\) 表示以 \(u\) 为根的子树所有节点到 \(u\) 的贡献。
\(dp2_u\) 表示 \(u\) 的子树外的点到 \(u\) 的贡献。
子节点 \(v\) 对 \(u\) 的贡献为
\(dp1[v] * mylog(w[u]) + siz[v] * w[u]\)
code
LL mylog(LL v)
{
if(v == 0) return 10;
int res = 0;
while(v) res ++, v /= 10;
return pow(10, res);
}
LL val(int u, int v) // u -> v 的贡献
{
return (dp1[u] * mylog(w[v]) + siz[u] * w[v]) % mod;
}
void dfs1(int u, int fa)
{
siz[u] = 1;
for(auto v : e[u])
if(v != fa)
{
dfs1(v, u);
siz[u] += siz[v];
dp1[u] = (dp1[u] + dp1[v]) % mod;
}
dp1[u] = (dp1[u] * mylog(w[u]) % mod + w[u] * siz[u] % mod) % mod;
}
void dfs2(int u, int fa)
{
for(auto v : e[u])
if(v != fa)
{
dp2[v] = ((dp1[u] + dp2[u] - val(v, u) - w[u]) % mod * mylog(w[v]) % mod + (siz[1] - siz[v] + 1) % mod * w[v] % mod) % mod;
dfs2(v, u);
}
}
code
void dfs1(int u, int fa)
{
// dp1[u] = dp1[v] + siz[v] * val[i];
siz[u] = c[u];
for(int i = h[u]; i; i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
dp1[u] += dp1[v] + siz[v] * val[i];
}
}
void dfs2(int u, int fa)
{
// 1->u dp2[u]=dp1[1]-siz[u]*val[i]+(siz[1]-siz[u])*val[i]
// u->v dp2[v](dp1[u]+dp2[u]-dp1[v]-siz[v]*val[i])+(siz[1]-siz[v])*val[i]
for(int i = h[u]; i; i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
dp2[v] = (dp1[u] + dp2[u] - dp1[v] - siz[v] * val[i]) + (siz[1] - siz[v]) * val[i];
dfs2(v, u);
}
}