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
本文为作者原创,转载请注明出处:本文链接
阅读量: