2020牛客暑期多校训练营Tokens on the Tree(树形DP，树链剖分)
题目描述
输入描述:
输出描述:
示例1
输入
2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2
输出
71
989
说明
题目大意
给定一棵树，这棵树上有黑白两种颜色，白色和黑色节点各构成了一坨连通块，其中一个节点可以将其颜色转移到它所在的连通块的外面一圈。
再定义一个函数，如果一个连通块通过变换能使得这个块的两端互换位置，那么称这两个形态为同种形态。现要求对于所有的，为树的大小，求的和乘上颜色各自的数量。
分析
首先剖析操作。想这样花里胡哨的描述，实际上是什么。其实就是一个连通块，它可以整块地在树上移动(或者用xinjun的话说是“蠕动”)。然后一团颜色在同一个区域里蠕动，算作一种。
一开始毫无头绪，所以不如先举几个例子来看看。
鲜艳起见，下文中使用红色和蓝色来表示黑和白。
我们来看上面的栗子。可以发现蓝色区域是无法移动的，由于红色区域大到占据了节点，即绿色节点。所以，一旦上面的情况发生，即如果红色的大到抢到了，那么就会造成蓝色只有待在一个地方不动。
那么这样的情况还是比较好处理的。只要找到树的，跑个树形就。
但是有种情况比较麻烦。
这样的时候蓝色就是海阔天空了，它啥地儿都能到。但是一旦红色又堵住了蓝色的路，那么它又没有去处了。这样搞起来就比较棘手。怎么办呢？
那就要用到树剖了。不妨我们把蓝色看成是挡路的，那么如果红色要到另一边去，那么蓝色必定是要让开至少一个节点使得红色可以通过。比如，上图中，前一张图蓝色就让路了，但是后一张就没有。那么对于一棵树，我们考虑红色(假使它比较大)，那么他肯定是要从左端到右端。那么怎么定义这个左右呢？显然，不能乱搞，我们要求出树的最长链，然后使一段为左另一端为右。
那么怎么求最长链，就可以求一下以树的重心为根的最长链和次长链，然后将它们连起来就可以了。于是就有一个美妙的解法。
首先，我们对这个树求重心，然后求出最长的链。那么我们只要在这条链上除了两端在中间找个子树把蓝色塞在里面，那么红色就可以通过了。
那么接下来我们想，解决了两种情况，那么分类讨论吗，好像无法分类啊。没问题，不用分类的。我们想，一旦红色占据了节点，不就转化为了上面的一种情况吗。那所以，两种情况是可以合在一起考虑的。
最后，综述一下这题应该怎么搞。首先枚举红色的大小，假定其大小大于蓝色，那么设大小为。同样的蓝色为。然后对于每个红色的大小，我只要用上面给出的算法，求一下所有的可能，然后算答案就可以了。思想是比较难想，
代码也很难写。
所以接下来，就看代码吧。
代码
有更多注释的我放在了这里。下面就只写一些必要的。
#include<bits/stdc++.h>
#define ll long long
#define debug cerr<<ans<<endl;
using namespace std;
const int MAXN=2e5+10;
const int MOD=1e9+7;
vector<int> vec[MAXN],sq;
pair<int,int> cog;
ll ans;
int n,vl[MAXN],vr[MAXN],vc[MAXN];
int siz[MAXN],dep[MAXN];
void predfs(int x,int fa,int depth)
{
siz[x]=1;dep[x]=depth;int mx=0;
for(int i=0;i<vec[x].size();i++){
int s=vec[x][i];
if(s==fa) continue;
predfs(s,x,depth+1);
siz[x]+=siz[s];mx=max(mx,siz[s]);
}mx=max(mx,n-siz[x]);
cog=min(cog,make_pair(mx,x));
}//没有确定重心，因此先predfs求重心
int get_siz(int x,int fa)
{
if(dep[x]>dep[fa]) return siz[x];return n-siz[fa];
}//这个玄幻的函数，求以fa为x父节点时的x的子树大小
void dfs(int x,int fa)
{
sq.push_back(x); int mx=0;
for(int i=0;i<vec[x].size();i++){
int s=vec[x][i];
if(s!=fa) mx=max(mx,get_siz(s,x));
}
for(int i=0;i<vec[x].size();i++){
int s=vec[x][i];
if(s!=fa&&get_siz(s,x)==mx)
{dfs(s,x);break;}
}
}//跑出最大的链
ll get_sum(ll s,ll t){return (s+t)%MOD*(t-s+1)/2%MOD;}
//求s加到t的结果
void dfs2(int x,int fa,int xx)
{
int y=get_siz(fa,x),z=n-y;
ans=(ans+get_sum(xx,y)%MOD*get_sum(1,z)%MOD*2ll%MOD)%MOD;
for(int i=0;i<vec[x].size();i++){
int s=vec[x][i];
if(s!=fa) dfs2(s,x,get_siz(fa,x)+1);
}
}//算答案
int main()
{
int T;
for(scanf("%d",&T);T--;){
scanf("%d",&n);
for(int i=0;i<=n;i++) vec[i].clear();
for(int i=1;i<n;i++){
int p;
scanf("%d",&p);p--;
vec[i].push_back(p);
vec[p].push_back(i);
}
cog=make_pair(n,-1);
predfs(0,-1,0);
int rt=cog.second;
sq.clear();
dfs(rt,-1);
reverse(sq.begin(),sq.end());
sq.pop_back();
dfs(rt,sq[sq.size()-1]);
multiset<int> st;
multiset<int>::iterator it;
//multiset 不去重的排序集合
for(int i=0;i<sq.size();i++){
int v=sq[i];
vl[i]=vr[i]=vc[i]=0;
for(int j=0;j<vec[v].size();j++){
int s=vec[v][j];
if(i>0&&sq[i-1]==s) vr[i]=n-get_siz(s,v);
else if(i+1<sq.size()&&sq[i+1]==s) vl[i]=n-get_siz(s,v);
else vc[i]=max(vc[i],get_siz(s,v));
}
st.insert(vc[i]);
}
int l=0,r=sq.size()-1;
ans=0;int big=1;
for(;;big++){//枚举big的大小
while(l<r&&vl[l]<big){
l++;if(l==r) break;
it=st.lower_bound(vc[l]);st.erase(it);
}//删除两端放不下红色的情况
while(l<r&&vr[r]<big){
r--;if(l==r) break;
it=st.lower_bound(vc[r]);st.erase(it);
}//同
if(l>=r) break;int mx=0;
if(!st.empty()){it=st.end();it--;mx=*it;}
ans=(ans+(ll)big%MOD*(ll)big%MOD*(mx>=big?1ll:2ll)%MOD)%MOD;
int small=min(mx,big-1);
ans=(ans+(ll)big%MOD*(ll)small%MOD*(small+1)%MOD)%MOD;
small=big-1;
if(mx<small)
ans=(ans+(ll)big%MOD*(ll)(small+mx+1)%MOD*(ll)(small-mx)%MOD*2ll%MOD)%MOD;
}
for(int i=0;i<vec[rt].size();i++){
int s=vec[rt][i];dfs2(s,rt,big);
}printf("%lld\n",ans);
}
}
DNE
本人蒟蒻，所以很多东西表达不好，如果有误解或者蒟蒻有错的地方，请各位直言，感谢~
听xinjun说是IOI级别的题，i了i了。