[CSP-S2019] 树上的数

这显然是一个树上贪心的问题。

[CSP-S2019] 划分

借助干草堆的思路：所叠层数最高时，其底层最窄。

不难写出状态转移方程：

f x = f y + 1 ( s u m x − s u m y > = g y ) f_x=f_y+1(sum_x-sum_y>=g_y) fx​=fy​+1(sumx​−sumy​>=gy​)

我们要求出满足条件且 f y f_y fy​最大时， y y y的最大值，然后令 g x = s u m x − s u m y g_x=sum_x-sum_y gx​=sumx​−sumy​

注意到 f y f_y fy​递增，所以我们只需要找到满足条件的 y y y的最大值就行了。

可以用单调队列优化，维护一个 s u m y + g y sum_y+g_y sumy​+gy​单调递增的序列即可。

顺便提一下，如果 s u m x sum_x sumx​没有单调递增的性质，可以用二分查找。

时间复杂度 O ( n ) O(n) O(n)。

本题的状态转移方程：

f x = f y + ( s u m x − s u m y ) 2 f_x=f_y+(sum_x-sum_y)^2 fx​=fy​+(sumx​−sumy​)2

稍微有点不同的地方在于，和上一个状态转移方程相比，转移代价不是常数1。

事实上我们可以知道：应该尽量让当前层的长度最小，同时能获得最小代价。

条件： s u m x − s u m y > = g y sum_x-sum_y>=g_y sumx​−sumy​>=gy​

⇔ s u m x > = s u m y + g y \Leftrightarrow sum_x>=sum_y+g_y ⇔sumx​>=sumy​+gy​

需要维护一个 s u m y + g y sum_y+g_y sumy​+gy​单调递增的序列。

如果要找的是最远点呢？那新加的点多半是没有用的。我们应该遵循新加的点一定有可能用上这一原则。

[CSP-S2019] Emiya 家今天的饭

要求合法的方案数，等于总方案数-不合法的方案数

设 f x , y f_{x,y} fx,y​ 表示前 x x x 种烹饪方法，做 y y y 道菜的方案数，总方案数可以 O ( n m ) O(nm) O(nm) 解决。

不合法的方案数=每种食材使用超过 ⌊ k 2 ⌋ \lfloor\frac{k}{2}\rfloor ⌊2k​⌋ 的并

注意到每种方案最多只有1种食材超过 ⌊ k 2 ⌋ \lfloor\frac{k}{2}\rfloor ⌊2k​⌋

设 g i , j , k , s g_{i,j,k,s} gi,j,k,s​ 表示前 i i i 个人，做了 j j j 道菜，至少选了 s s s 次 k k k 食材的方案数

时间复杂度 O ( n 3 m ) O(n^3m) O(n3m)。

我们发现枚举统计答案是 O ( n m ) O(nm) O(nm) ，预处理是 O ( n 3 m ) O(n^3m) O(n3m)，考虑平衡时间复杂度。

容易发现 j , s j,s j,s 有联系，可以用 2 ∗ k − j 2*k-j 2∗k−j表示超过半数，这样就变成 O ( n 2 m ) O(n^2m) O(n2m) 了。

-j<=2*k-j<=j

0<=2k-j+j<=2j

[CSP-S2019] 树的重心

读题。。。

考虑暴力。枚举边(u,v)，分别以u,v为起点向子树寻找重心，每次走向一个重儿子，直到找到重心。

这个算法在子树不平均或链的形态时会退化成O(nm)

考虑树链剖分。

注意到树链剖分都是指向重儿子。

如果这是一个静态问题，那么记录 s o n x son_x sonx​， s o n 2 x son2_x son2x​， s i z x siz_x sizx​， f x , y f_{x,y} fx,y​ 表示重儿子的 2 y 2^y 2y 路径即可。

由于是动态问题，所以需要 O ( l o g n ) O(logn) O(logn) 维护上述信息。

当 d f s y dfs_y dfsy​ 时，把 y y y 作为根；当 y y y 回溯时，又把 x x x 作为根，同时更新 f f f 数组。

幸好有维护数据结构的功底，不过还是维护了很久。

注意跳的时候不是判断是否合法，而是其上方子树<= ⌊ s u m 2 ⌋ \lfloor\frac{sum}{2}\rfloor ⌊2sum​⌋

而且重构的时候不能中途break，必须更新完。

tips：最开始只对son_x值有改变的进行了重构，实际操作中u，v都必须重构，否则会出错。

还是没有想明白一个细节：为什么u,v都必须重构。。。

#include<bits/stdc++.h>
using namespace std;
const int mx=3e5+5;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
int n;
int head[mx*2],nxt[mx*2],to[mx*2],cnt;
int f[mx][20];
int c[mx];
int siz[mx],son[mx],son2[mx],fa[mx];
long long ans;
bool judge(int x,int sum) {
	return (max(siz[son[x]],sum-siz[x])<=sum/2);
}
void add(int x,int y) {to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;}
void put(int x,int y,int z) {
//	printf("%d %d %d\n",x,y,z);
    c[z]++;
}
void build(int x) {
	f[x][0]=son[x];
	for(int i=1;i<=19;i++) {
		f[x][i]=f[f[x][i-1]][i-1];
	}
}
void dfs(int x,int fath) {
	fa[x]=fath,siz[x]=1;
	for(int i=head[x];i;i=nxt[i]) {
		int y=to[i]; if(y==fath) continue;
		dfs(y,x),siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son2[x]=son[x],son[x]=y;
		else if(siz[y]>siz[son2[x]]) son2[x]=y;
	}
	build(x);
}
void dfs2(int u,int fath) {
//	printf("dfn:%d\n",u);
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i]; if(v==fath) continue;
		//查询v所在子树 
		int x=v;
		for(int j=19;j>=0;j--) {
			int y=f[x][j];
			if(siz[v]-siz[y]<=siz[v]/2) x=y;
		}
		if(judge(x,siz[v])) ans+=x,put(u,v,x);
		if(x!=v&&judge(fa[x],siz[v])) ans+=fa[x],put(u,v,fa[x]);
		//改变父子关系
		siz[u]-=siz[v],siz[v]+=siz[u],fa[u]=v;
		if(siz[u]>siz[son[v]]) {
			son2[v]=son[v],son[v]=u;
		}
		else if(siz[u]>siz[son2[v]]) {
//			printf("%d\n",son2[v]);
			son2[v]=u;
		}
		if(son[u]==v) {
            //这里son2必须清零，我也不知道为什么
            //原因见函数倒数第二排，son和son2会指向同一个数
			son[u]=son2[u],son2[u]=0;
		}
		build(u),build(v);
		//查询u所在子树
//		int mxtree=siz[son[u]];
//		if(mxtree<=siz[u]/2) ans+=u,putc(u,v,u,1);
//		x=son[u]; 
        x=u;
		for(int i=19;i>=0;i--) {
			int y=f[x][i];
			if(siz[u]-siz[y]<=siz[u]/2) x=y;
		}
//		if(x&&siz[son[x]]<=siz[u]/2&&siz[u]-siz[x]<=siz[u]/2) {
//			printf("pos:%d val:%d %d %d\n",u,x,siz[x],siz[u]);
			if(judge(x,siz[u])) ans+=x,put(u,v,x);
			if(x!=u&&judge(fa[x],siz[u])) ans+=fa[x],put(u,v,fa[x]);
//		}
		dfs2(v,u);
		//还原父子关系
        //我们称之为回溯操作
		siz[v]-=siz[u],siz[u]+=siz[v],fa[v]=u,fa[u]=0;
		if(son[v]==u) {
			son[v]=son2[v],son2[v]=0;
		}
		if(siz[v]>siz[son[u]]) {
//			if(son[u]==son2[u]) printf("yes");
			son2[u]=son[u],son[u]=v;
		}
		else if(siz[v]>siz[son2[u]]) son2[u]=v;
		build(u),build(v);
	}
}
int main() {
	freopen("centroid.in","r",stdin);
	freopen("centroid.out","w",stdout);
    int T=read();
    while(T--) {
    	memset(f,0,sizeof(f));
    	memset(son,0,sizeof(son));
    	memset(son2,0,sizeof(son2));
    	memset(head,0,sizeof(head));
    	memset(c,0,sizeof(c));
        n=read(); cnt=ans=0;
        for(int i=1;i<n;i++) {
        	int x=read(),y=read();
        	add(x,y),add(y,x);
		}
		dfs(1,0);
		dfs2(1,0);
		printf("%lld\n",ans);
//		for(int i=1;i<=n;i++) printf("%d ",c[i]);
//		printf("\n");
	}
}