鲜花网站建设店,做宠物网站导航应该写什么字,php网站后台建设,小程序登录入口qq浏览器2021牛客OI赛前集训营-提高组#xff08;第四场#xff09;
题目大意
有一棵n1n1n1个节点的树#xff0c;根节点为0。给你一个kkk#xff0c;定义集合Si{j∈Z∣max(1,i−k)≤ji}∪{0}S_i\{j\in Z|\max(1,i-k)\leq ji\}\cup\{0\}Si{j∈Z∣max(1,i−k)≤ji…2021牛客OI赛前集训营-提高组第四场
题目大意
有一棵n1n1n1个节点的树根节点为0。给你一个kkk定义集合Si{j∈Z∣max(1,i−k)≤ji}∪{0}S_i\{j\in Z|\max(1,i-k)\leq ji\}\cup\{0\}Si{j∈Z∣max(1,i−k)≤ji}∪{0}。
Ai∑j∈Sidis(i,j)2A_i\sum\limits_{j\in S_i}dis(i,j)^2Aij∈Si∑dis(i,j)2dis(i,j)dis(i,j)dis(i,j)指iii到jjj在树上的距离。求A1,A2,…,AnA_1,A_2,\dots,A_nA1,A2,…,An分别是多少。 题解
令aia_iai表示iii在树上的深度注意根节点的深度为1。
那么dis(i,j)2(aiaj−2alca)2ai2aj22aiaj−4alcaai−4alcaaj4alca2dis(i,j)^2(a_ia_j-2a_{lca})^2a_i^2a_j^22a_ia_j-4a_{lca}a_i-4a_{lca}a_j4a_{lca}^2dis(i,j)2(aiaj−2alca)2ai2aj22aiaj−4alcaai−4alcaaj4alca2
我们可以枚举iii用树链剖分来维护jjj的值。
对于ai2a_i^2ai2可以直接得出。
对于aj2a_j^2aj2将所有在SiS_iSi中的jjj求前缀和即可。
对于2aiaj2a_ia_j2aiaj对aja_jaj求前缀和再乘上2ai2a_i2ai。
对于4alcaai4a_{lca}a_i4alcaai对每个SiS_iSi中的jjj都将jjj到根节点的路径上的点加1然后查询iii到根节点的路径上的对应值的和再乘上4ai4a_i4ai即可。
对于4alcaaj4a_{lca}a_j4alcaaj对每个SiS_iSi中的jjj都将jjj到根节点的路径上的点加aja_jaj然后查询iii到根节点的路径上的对应值的和再乘上444即可。
对于4alca24a_{lca}^24alca2对每个SiS_iSi中的jjj都将jjj到根节点的路径上的点加ak∗2−1a_k*2-1ak∗2−1kkk表示当前节点然后查询iii到根节点的路径上的对应值的和因为x2135⋯(x∗2−1)x^2135\cdots(x*2-1)x2135⋯(x∗2−1)所以这样求出的就是alca2a_{lca}^2alca2然后乘444即可。
对于jjj进入集合或离开集合在jjj到根节点的路径上进行区间修改即可。
为什么根节点的深度为1而不为0呢因为只有根节点的深度为1那么每个点到根节点的路径的长度才能等于这个点的深度这样才能更好地实现。
时间复杂度为O(nlog2n)O(n\log^2 n)O(nlog2n)。
code
#includebits/stdc.h
#define lc k1
#define rc k1|1
using namespace std;
int n,k,x,y,tot0,d[500005],l[500005],r[500005],dep[500005],fa[500005],siz[500005],son[500005];
int tp[200005],s[200005],re[200005];
long long ans,hv1[800005],hv2[800005],mx1[800005],mx2[800005],mx3[800005],ly1[800005],ly2[800005],ly3[800005];
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void dfs1(int u,int f){fa[u]f;dep[u]dep[f]1;siz[u]1;for(int ir[u];i;il[i]){if(d[i]f) continue;dfs1(d[i],u);siz[u]siz[d[i]];if(siz[d[i]]siz[son[u]]) son[u]d[i];}
}
void dfs2(int u,int f){if(son[u]){tp[son[u]]tp[u];s[son[u]]s[0];re[s[0]]son[u];dfs2(son[u],u);}for(int ir[u];i;il[i]){if(d[i]f||d[i]son[u]) continue;tp[d[i]]d[i];s[d[i]]s[0];re[s[0]]d[i];dfs2(d[i],u);}
}
void build(int k,int l,int r){if(lr){hv1[k]2ll*dep[re[l]]-1;hv2[k]1ll;return;}int midlr1;build(lc,l,mid);build(rc,mid1,r);hv1[k]hv1[lc]hv1[rc];hv2[k]hv2[lc]hv2[rc];
}
void down(int k){mx1[lc]ly1[k]*hv1[lc];ly1[lc]ly1[k];mx2[lc]ly2[k]*hv2[lc];ly2[lc]ly2[k];mx3[lc]ly3[k]*hv2[lc];ly3[lc]ly3[k];mx1[rc]ly1[k]*hv1[rc];ly1[rc]ly1[k];mx2[rc]ly2[k]*hv2[rc];ly2[rc]ly2[k];mx3[rc]ly3[k]*hv2[rc];ly3[rc]ly3[k];ly1[k]ly2[k]ly3[k]0;
}
void ch(int k,int l,int r,int x,int y,long long t,int u){if(lxry){mx1[k]t*hv1[k];ly1[k]t;mx2[k]t*hv2[k];ly2[k]t;mx3[k]t*dep[u]*hv2[k];ly3[k]t*dep[u];return;}if(ly||rx) return;if(lr) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int midlr1;if(xmid) ch(lc,l,mid,x,y,t,u);if(ymid) ch(rc,mid1,r,x,y,t,u);mx1[k]mx1[lc]mx1[rc];mx2[k]mx2[lc]mx2[rc];mx3[k]mx3[lc]mx3[rc];
}
void find(int k,int l,int r,int x,int y,int u){if(lxry){ans4ll*(mx1[k]-mx2[k]*dep[u]-mx3[k]);return;}if(ly||rx) return;if(lr) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int midlr1;if(xmid) find(lc,l,mid,x,y,u);if(ymid) find(rc,mid1,r,x,y,u);
}
void ask(int i){int ti;while(i1){find(1,1,s[0],s[tp[i]],s[i],t);ifa[tp[i]];}
}
void ins(int i){int ti;while(i1){ch(1,1,s[0],s[tp[i]],s[i],1,t);ifa[tp[i]];}
}
void del(int i){int ti;while(i1){ch(1,1,s[0],s[tp[i]],s[i],-1,t);ifa[tp[i]];}
}
int main()
{scanf(%d%d,n,k);n;for(int i1;in;i){scanf(%d%d,x,y);x;y;add(x,y);add(y,x);}dfs1(1,0);s[1]s[0];re[s[0]]1;tp[1]1;dfs2(1,0);build(1,1,s[0]);long long sum10,sum20;for(int i2,vt,vk2;in;i){vtmax(2,i-k);while(vkvt){sum1-1ll*dep[vk]*dep[vk];sum2-1ll*dep[vk];del(vk);vk;}ans1ll*(dep[i]-1)*(dep[i]-1)1ll*(i-vt)*dep[i]*dep[i]sum12ll*dep[i]*sum2;ask(i);printf(%lld\n,ans);sum11ll*dep[i]*dep[i];sum21ll*dep[i];ins(i);}return 0;
}
