首页 > 其他分享 >8.30 模拟赛 光和影(dream) 题解

8.30 模拟赛 光和影(dream) 题解

时间:2023-09-03 21:55:07浏览次数:63  
标签:siz ch int 题解 up fa maxn 光和影 dream

概括:大分类讨论。

首先有个重要结论,无论是三种操作中的哪一种,他的左儿子仍然在他的左子树内,右儿子在右子树内。同时,旋转一个点一次,对他更上面的点的深度没有影响。

以此,我们预处理出一个 \(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

相关文章

  • CF838D Airplane Arrangements 题解
    题意一架飞机有\(n\)个座位排成一列,有\(m\)名乘客(\(m\leqn\))依次上飞机。乘客会选择一个目标座位(两人可以选同一个目标座位),然后选择从前门或者后门上飞机,上飞机后,他们会走到自己的目标座位,如果目标座位已经有人坐了,他们会继续往前走,在走到第一个空位后坐下。如果走到最后......
  • 【题解】P2900 [USACO08MAR] Land Acquisition G
    题目链接:P2900[USACO08MAR]LandAcquisitionG我们通过题目可以得出一个较为清晰的结论:我们将所有的矩形排列起来,可以发现最后被完全包含在另一个矩形内的矩形是没有意义的。这样的话我们得到的所有矩形的并是呈阶梯状的,如下图:其中,中间的浅蓝色的边是没有意义的然后我......
  • [ABC318G] Typical Path Problem 题解
    题意给定一个\(N\)个节点和\(M\)条边组成的简单无向联通图,给定三个节点\(A,B,C\),求是否存在一条简单路径满足\(A\rightarrowB\rightarrowC\)。(\(3\leN,M\le2\times10^5\))。题解因为简单路径要求每个节点至多经过一次,故不存在合法的简单路径当且仅当存在一个......
  • 【动态规划】“新手动态规划合集”题解
    动态规划三要素阶段,状态,决策动态规划经典模型LIS(最长上升子序列)给定长度为\(N\)的序列\(A[i]\),求出其最长上升子序列的长度。(以不严格上升为例)阶段:已经处理的序列长度\(i\)状态:\(f[i]\)表示以\(A[i]\)结尾的LIS长度转移\[f[i]=\max\limits_{j\in\left[1,......
  • [ABC318D] General Weighted Max Matching 题解
    [ABC318D]GeneralWeightedMaxMatching题解题意  给定无向有权完全图,求最大权匹配。思路分析  注意到\(n\le16\),我考虑状压DP。  设当前点集\(S\)中最大权匹配的答案是\(f_S\),我们考虑\(S\)中“最后”一个点\(p\)(这里的“最后”一个点是指,在状压表示状态......
  • [ABC318E] Sandwiches 题解
    题意给定一个长度为\(N\)的正整数列\(A=\left(A_1,A_2,\cdots,A_N\right)\),求满足以下条件的正整数三元组\(\left(i,j,k\right)\)的数量:\(1\lei<j<k\leN\);\(A_i=A_k\);\(A_i\neqA_j\)。数据范围:\(3\leN\le3\times10^5\);\(1\leA_i......
  • CF1848B Vika and the Bridge 题解
    CF1848BVikaandtheBridge题解题目大意给个题目传送门吧,感觉题意已经很清楚了题目传送门分析(我不会告诉你我第一眼看过去是二分)因为我们只能改一块木板的颜色,所以可以考虑贪心。大概算了下复杂度,也没有问题。题解我们要去求每种颜色最大距离的最小值,那我们可以先去求......
  • 有关Vue-Cli5.X工程中ESLint组件命名检查问题解决
    个人开发环境简介,工具用的VisualStudioCode,因为每个人的开发环境不同,不可能所有解决方案通用,防止踩坑。PSF:\VueWorkSpace\vue_router_test>node-vv16.12.0PSF:\VueWorkSpace\vue_router_test>npm-v8.1.0PSF:\VueWorkSpace\vue_router_test>npmeslint-v8.1.0......
  • P3604 美好的每一天题解
    传送门好题!首先说这道题的时间复杂度:\(O(26n\sqrtn)\)。因为转移是的常数是\(O(26)\)并非\(O(1)\),这启示我们,看数据范围,不要被O(1)给限制了,O(1)是一般情况,有些题不一般首先,回文串能出现的条件是所有的字符都出现偶数次\(or\)仅有一个字符出现奇数次,所以我们并不关心每个......
  • 【题解】AtCoder Beginner Contest 318(D - Ex)
    赛时过了A-G,Ex仿佛猜到了结论但是完全不懂多项式科技,就炸了。大家好像都秒了A,B,C就不写了。D.GeneralWeightedMaxMatching题目描述:给你一个加权无向完全图,图中有\(N\)个顶点,编号从\(1\)到\(N\)。连接顶点\(i\)和\(j\)的\((i<j)\)的权重为\(D_{i,j}\)。在......