概括:大分类讨论。
首先有个重要结论,无论是三种操作中的哪一种,他的左儿子仍然在他的左子树内,右儿子在右子树内。同时,旋转一个点一次,对他更上面的点的深度没有影响。
以此,我们预处理出一个 \(up_{u,0/1}\) 表示将 \(u\) splay 到根上,对左子树和右子树深度的影响,由于上面的结论,这个东西可以dfs求出。
然后,如果我们能将点对 \((x,y)\) 表示 splay \(y\) 对 \(x\) 的影响表示为 \(up\) 有关的形式,你就可以求了。
发现这东西的影响可以分成对兄弟子树的影响,对父亲的兄弟的子树的影响,祖先的影响,儿子的影响,儿子的儿子的影响这几种,然后分类讨论即可。具体细节很多,在代码里有。
由于旋转一个点不会给对更上的点产生影响,所以某些情况可以根据深度奇偶性划分到上面几种情况。
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO {
struct IO {
char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
IO() : iS(ibuf), iT(ibuf), oS(obuf) {} ~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == 't' || ch == EOF; }
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void read (char *s) {
char ch = gh(); int l = 0;
while (eof(ch)) ch = gh();
while (!eof(ch)) s[l++] = ch, ch = gh();
}
inline void read (double &x) {
char ch = gh(); bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
if (ch != '.') return t && (x = -x), void(); ch = gh();
for (double cf = 0.1; '0' <= ch && ch <= '9'; ch = gh(), cf *= 0.1) x += cf * (ch ^ 48);
t && (x = -x);
}
inline void pc (char ch) {
#ifdef ONLINE_JUDGE
if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
*oS++ = ch;
#else
putchar(ch);
#endif
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
inline void write (char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) pc(s[i]);
}
} io;
inline long long read () { return io.read(); }
template<typename Tp>
inline void read (Tp &x) { io.read(x); }
template<typename _Tp>
inline void write (_Tp x) { io.write(x); }
}
const int mod=1e9+7;
using namespace FastIO;
const int maxn=1e6+10;
int dep[maxn],siz[maxn][2],fat[maxn],ffat[maxn],d[maxn],n,ans[maxn],td[maxn];
int bot[maxn];
vector<int> G[maxn];
int ch[maxn][2];
inline int pos(int u){return ch[fat[u]][1]==u;}
inline int gettype(int u){if(!fat[u])return 0;if(!ffat[u])return 1;if(pos(u)==pos(fat[u]))return 2;return 3;}
int up[maxn][2];
void predfs(int u,int fa)
{
siz[u][0]=1;
dep[u]=dep[fa]+1;
fat[u]=fa;ffat[u]=fat[fa];
int type=gettype(u),op=pos(u);
if(type==0)up[u][0]=up[u][1]=0;
else if(type==1)up[u][op]=-1,up[u][!op]=0;
else if(type==2)up[u][op]=-2+up[ffat[u]][op],up[u][!op]=-1+up[ffat[u]][!op];
else up[u][0]=up[ffat[u]][0]-1,up[u][1]=up[ffat[u]][1]-1;
if(ch[u][0])
{
int v=ch[u][0];
predfs(v,u);
siz[u][0]+=siz[v][1];
siz[u][1]+=siz[v][0];
}
if(ch[u][1])
{
int v=ch[u][1];
predfs(v,u);
siz[u][0]+=siz[v][1];
siz[u][1]+=siz[v][0];
}
}
void dfs(int u,int fa)
{
d[u]+=d[fa];
td[u]+=td[fa];
ans[u]+=d[u]+td[u];
if(ch[u][0])dfs(ch[u][0],u);
if(ch[u][1])dfs(ch[u][1],u);
}
signed main()
{
//freopen("dream11.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)ch[i][0]=read(),ch[i][1]=read(),bot[ch[i][0]]=ch[i][1],bot[ch[i][1]]=ch[i][0];
predfs(1,0);
for(int u=1;u<=n;u++)
{
int op=pos(u);
if(bot[u])//旋转兄弟
{
int typ=gettype(bot[u]);
if(typ==1)d[u]+=1*siz[bot[u]][0];//兄弟zig
if(typ==2)d[u]+=(1+up[ffat[u]][op])*siz[bot[u]][0];//兄弟zig-zig
if(typ==3)d[u]+=(up[ffat[u]][op])*siz[bot[u]][0];//兄弟zig-zag
}
if(bot[u]&&ch[bot[u]][!op])//兄弟儿子zig-zig
d[u]+=(up[fat[u]][op]+2)*siz[ch[bot[u]][!op]][0];
if(bot[u]&&ch[bot[u]][op])//兄弟儿子zig-zag
d[u]+=(up[fat[u]][op]+1)*siz[ch[bot[u]][op]][0];
if(ch[u][0])td[ch[u][0]]+=up[u][0];//祖先
if(ch[u][1])td[ch[u][1]]+=up[u][1];
if(ch[u][0])//旋到儿子
{
int v=ch[u][0];
int typ=gettype(v);
if(typ==1)ans[u]+=1*siz[v][0];
if(typ==2)ans[u]+=up[fat[u]][!op]*siz[v][0];
if(typ==3)ans[u]+=up[fat[u]][op]*siz[v][0];
}
if(ch[u][1])//旋到儿子
{
int v=ch[u][1];
int typ=gettype(v);
if(typ==1)ans[u]+=1*siz[v][0];
if(typ==2)ans[u]+=up[fat[u]][!op]*siz[v][0];
if(typ==3)ans[u]+=up[fat[u]][op]*siz[v][0];
}
if(ch[u][0])//旋到儿子的儿子
{
int v=ch[u][0];
if(ch[v][0])ans[u]+=siz[ch[v][0]][0]*(2+up[u][1]);
if(ch[v][1])ans[u]+=siz[ch[v][1]][0]*(1+up[u][1]);
}
if(ch[u][1])//旋到儿子的儿子
{
int v=ch[u][1];
if(ch[v][1])ans[u]+=siz[ch[v][1]][0]*(2+up[u][0]);
if(ch[v][0])ans[u]+=siz[ch[v][0]][0]*(1+up[u][0]);
}
}
dfs(1,0);
for(int i=1;i<=n;i++)write((ans[i]+(dep[i]-1)*(n-1))%mod),io.pc('\n');
return 0;
}
标签:siz,ch,int,题解,up,fa,maxn,光和影,dream
From: https://www.cnblogs.com/hikkio/p/17675666.html