CF1260F Colored Tree
题意
一颗有 n 个节点的树，每个节点 v 有颜色 $c_v$，这个染色方案的权值为 $\sum\limits_{u,v\in[1,n],v>u,c_v=c_u}\operatorname{dis}{(u,v)}$。
现在知道每个节点 v 可以染成 $[l_v,r_v]$ 中任意颜色，求所有染色方案的权值之和。
$n\le 10^5$，时限 2.5 秒。
思路
一个显然的想法是考虑每一条路径的贡献，于是自然的想到点分治。考虑过分治中心一条路径的贡献（为方便起见，后文都算的是权值期望）。
显然贡献为：
\[(d_u+d_v)\frac{|[l_u,r_u]\cap[l_v,r_v]|}{|[l_u,r_u]|\cdot|[l_v,r_v]|}\]我们可以维护一个线段树，在搜到 u 的时，把 $[l_u,r_u]$ 区间加 $\frac{d_u}{|[l_u,r_u]|}$。搜到 v 时，把 $[l_v,r_v]$ 区间的和，乘以 $\frac1{|[l_v,r_v]|}$，加到答案里即可，这样我们就解决了上式中第一项。
对于第二项，可以反着做一遍，也可以再开一个另外含义的线段树，怎么搞都行。
复杂度 $\mathcal{O}(n\log^2 n)$。
题解提供了一个不用点分治的做法，复杂度一样，在此先不说，因为我没读懂。
代码
const ll INF=1e18,P=1e9+7;
inline ll mod(ll x){
if(x>=P)return x-P;
if(x<0)return x+P;
return x;
}
inline ll qpow(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%P;x=x*x%P;y>>=1;}return res;}
const ll MXN=1e5+5,MNMEM=5e4;
ll n,ans,all=1,arr[MXN],lh[MXN],rh[MXN];
struct tarr{
ll d[MXN],di[MXN];
inline void suf(ll x,ll y){
ll yi=y*x%P;
for(;x<MXN;x+=x&(-x)){
d[x]=mod(d[x]+y);
di[x]=mod(di[x]+yi);
}
}
inline ll pre(ll l){
ll s=0,si=0;
for(ll x=l;x;x^=x&(-x)){
s=mod(s+d[x]);
si=mod(si+di[x]);
}
return (s*(l+1)-si)%P;
}
inline void clr(ll x){for(;x<MXN;x+=x&(-x))d[x]=di[x]=0;}
inline void mem(){
memset(d,0,sizeof(d));
memset(di,0,sizeof(di));
}
}c,v;
vector<ll> t[MXN];
ll sz[MXN];bool vis[MXN];
inline void dfssz(ll p,ll fa){
sz[p]=1;
for(ll &nx:t[p])
if(!vis[nx] && nx!=fa){
dfssz(nx,p);
sz[p]+=sz[nx];
}
}
inline ll dfsrt(ll p,ll fa,ll tot){
bool f=(sz[p]<<1)>=tot;
for(ll &nx:t[p])
if(!vis[nx] && nx!=fa){
ll tmp=dfsrt(nx,p,tot);
if(tmp)return tmp;
f&=(sz[nx]<<1)<=tot;
}
return f?p:0;
}
inline void dfsm(ll p,ll fa,ll dpth){
if(dpth<0){
c.clr(lh[p]),c.clr(rh[p]+1);
v.clr(lh[p]),v.clr(rh[p]+1);
}
else{
ll tmp=dpth*arr[p]%P;
c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
v.suf(lh[p],tmp),v.suf(rh[p]+1,-tmp);
}
for(ll &nx:t[p])
if(!vis[nx] && nx!=fa)
dfsm(nx,p,dpth+1);
}
inline void dfsq(ll p,ll fa,ll dpth){
ans=(ans+(dpth*(c.pre(rh[p])-c.pre(lh[p]-1))+v.pre(rh[p])-v.pre(lh[p]-1))%P*arr[p])%P;
for(ll &nx:t[p])
if(!vis[nx] && nx!=fa)
dfsq(nx,p,dpth+1);
}
inline void dfz(ll p){
dfssz(p,0);
ll tsz=sz[p];
vis[p=dfsrt(p,0,tsz)]=1;
c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
for(ll &nx:t[p])
if(!vis[nx]){
dfsq(nx,0,1);
dfsm(nx,0,1);
}
if(tsz>MNMEM)c.mem(),v.mem();
else dfsm(p,0,-INF);
for(ll &nx:t[p])
if(!vis[nx])
dfz(nx);
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",lh+i,rh+i);
arr[i]=qpow(rh[i]-lh[i]+1,P-2);
all=all*(rh[i]-lh[i]+1)%P;
}
for(ll i=1,ts,tt;i<n;i++){
scanf("%lld%lld",&ts,&tt);
t[ts].pb(tt);
t[tt].pb(ts);
}
dfz(1);
printf("%lld\n",all*(ans+P)%P);
return 0;
}
树上游戏
实在找不到啥点分治好题了，只能用点分治硬做这题。
题意
树上每个点有颜色，定义 $\operatorname{s}{(i,j)}$ 为 i 到 j 路径颜色数，对于 $i\in[1,n]$ 求 $ans_i=\sum\limits_{j\in[1,n]}\operatorname{s}{(i,j)}$。
$n\le10^5$，时限 1 秒。
思路
这题怎么做都行，有好多线性的做法，但是我们要有拿下最劣解的追求，为了实现这一目标，考虑淀粉质的做法。
上图中，蓝色大三角表示所有搜过的子树，v 是正在查询的点，对于所有过分治中心 rt 的路径 $u \sim v$，考虑红色对哪些路径有贡献，发现有两种情况：
- u 在某个红色节点的子树中
- $v \sim rt$ 上有红色节点
定义 hasc 表示（蓝色子树中）到 rt 的路径上有红色的点数，当我修改节点 u 的时候，如果发现路径 $rt\sim u$ 上没有红色的话，我就 $hasc\gets hasc + \text{u 子树大小}$。
在查询时,一开始的答案为 hasc ，dfs 的过程中，如果第一次碰到一个红色点（这个点的祖先上没有红色点），那么对于其子树，红色的贡献就增加了蓝色区域的点数，回溯的时候再撤销即可。
因为每个点只有一个颜色，所以其实上述的过程是可以在 dfs 中对每个颜色同时进行的。
复杂度 $O(n\log n)$。
有不少细节，尤其是在分治中心的处理上，不建议实现。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 1e5 + 5;
ll n, c[MXN];
vector<ll> g[MXN];
bool vis[MXN];
ll sz[MXN];
void dfssz(ll p, ll fa) {
sz[p] = 1;
for (ll nx : g[p])
if (!vis[nx] && nx != fa) {
dfssz(nx, p);
sz[p] += sz[nx];
}
}
ll dfsrt(ll p, ll fa, ll tot) {
bool f = (sz[p] << 1) >= tot;
for (ll nx : g[p])
if (!vis[nx] && nx != fa) {
ll nxr = dfsrt(nx, p, tot);
if (nxr) return nxr;
f &= (sz[nx] << 1) <= tot;
}
return f ? p : 0;
}
ll instk[MXN], ans[MXN];
//到根路径上有这个颜色的节点数
ll hasc[MXN], curans;
void dfsm(ll p, ll fa, ll tp) {
if (!instk[c[p]]++) {
hasc[c[p]] += tp * sz[p];
curans += tp * sz[p];
}
for (ll nx : g[p])
if (!vis[nx] && nx != fa) dfsm(nx, p, tp);
--instk[c[p]];
}
void dfsq(ll p, ll fa, ll outofsubt) {
if (!instk[c[p]]++) curans += outofsubt - hasc[c[p]];
ans[p] += curans;
for (ll nx : g[p])
if (!vis[nx] && nx != fa) dfsq(nx, p, outofsubt);
if (!--instk[c[p]]) curans -= outofsubt - hasc[c[p]];
}
void dfz(ll p) {
dfssz(p, 0);
p = dfsrt(p, 0, sz[p]);
vis[p] = 1;
dfssz(p, 0);
instk[c[p]] = 1;
for (ll nx : g[p])
if (!vis[nx]) dfsm(nx, p, 1);
//到根
ans[p] += curans + sz[p];
for (ll nx : g[p])
if (!vis[nx]) {
dfsm(nx, p, -1);
curans += sz[p] - sz[nx];
dfsq(nx, p, sz[p] - sz[nx]);
curans -= sz[p] - sz[nx];
dfsm(nx, p, 1);
}
for (ll nx : g[p])
if (!vis[nx]) dfsm(nx, p, -1);
instk[c[p]] = 0;
for (ll nx : g[p])
if (!vis[nx]) dfz(nx);
}
int main() {
scanf("%lld", &n);
for (ll i = 1; i <= n; i++) scanf("%lld", c + i);
for (ll i = 1; i < n; i++) {
ll u, v;
scanf("%lld%lld", &u, &v);
g[v].push_back(u);
g[u].push_back(v);
}
dfz(1);
for (ll i = 1; i <= n; i++) printf("%lld\n", ans[i]);
return 0;
}
P3060 [USACO12NOV]Balanced Trees G
题意
给出一棵树，每个节点上有一个括号，对于所有括号匹配的路径，求其嵌套层数最大值。
思路
括号匹配比较有用的性质就是把 { 看成 1，} 看成 -1，最终序列的前缀和 $pre_i$都大于等于 0，并且总和 s 为 0.
而最大嵌套层数则等于前缀和的最大值。
考虑把两个括号序列合起来：
\[\begin{aligned} str&=str1 + str2\cr s&=s1+s2\cr \max{(pre_i)}&=\max{(\max{(pre1_i)},s1+\max{(pre2_i)})}\cr \min{(pre_i)}&=\min{(\min{(pre1_i)},s1+\min{(pre2_i)})} \end{aligned}\]所以只需在第一次 dfs 时，判断如果前半段 pre 的最小值大于等于 0，就把前半段 pre 的最大值打到一个桶里 s1 的位置，查询就随便搞搞即可。
没时间实现了，我妈催我睡觉😡。
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: