Educational Codeforces Round 82[CF1303]

发表于 分类于

比赛链接

链接

题目

Problem A~C

SB题，不写了。

Problem D

题意

懒得写了。

题解

显然贪心地从低位到高位维护当前能组成多少个 $2^i$ 即可。

Problem E

题意

给两个字符串 $s,t$，要求在 $s$ 中选出至多两个互不重合的子序列，按顺序排列后组成 $t$。问是否可行。

$|S|,|T|\leq 400$

题解

显然先枚举 $t$ 在哪个位置断开。

然后DP，设 $f[i][j][k]$ 表示前 $i$ 位两个子串分别匹配到第 $j,k$ 位是否可行。

时间复杂度 $O(n^4)$。需要优化。

因为DP值只有 $0,1$ 两种情况，因此可以降一维，设 $f[i][j]$ 为前 $i$ 为第一个子串匹配到第 $j$ 位时，第二个子串最大匹配到的位置。

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

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N=405;
int n,m,f[N][N];
char s[N],t[N];
inline void getmax(int &x,int y){x=max(x,y);}
int main()
{
	CASET
	{
		scanf("%s",s+1);
		scanf("%s",t+1);
		n=strlen(s+1); m=strlen(t+1);
		bool flag=0;
		fo(k,1,m)
		{
			fo(i,0,n+1) fo(j,0,m+1) f[i][j]=-1;
			f[0][0]=0;
			fo(i,1,n)
			{
				fo(j,0,min(k,i))
				{
					if(i>j&&f[i-1][j]>=0) getmax(f[i][j],f[i-1][j]+(f[i-1][j]>=m-k?0:(t[k+1+f[i-1][j]]==s[i]?1:0)));
					if(j&&f[i-1][j-1]>=0&&s[i]==t[j]) getmax(f[i][j],f[i-1][j-1]);
				}
			}
			flag|=(f[n][k]==m-k);
			if(flag) break;
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

Problem F

题意

懒得写了。

题解

考虑某个点改变颜色后，对于原来的颜色集合，相当于删除操作，对于改变后的颜色的集合，相当于添加操作。

删除操作可以用时间倒流，变成添加操作，因此只需考虑添加。

对于每种颜色分开考虑，若加上一个点，考虑此时连通块数量的变化情况。

若这个点有 $x$ 个连通块与之相邻，则新增的连通块数为 $1-x$。

并查集+时间倒流即可。

Problem G

题意

一棵树，有点权。任选 $u,v$，求从 $u$ 到 $v$ 路径所形成的点权的序列的后缀和的和的最大值。

$n\leq 1.5\times 10^5$，时限 $6s$。

题解

一个序列 ${a_1,a_2,\cdots,a_k}$ 的权值为：$\sum_{i=1}^ki\times a_i$。考虑如何在树上求最大值。

跟树上路径有关系的，显然点分治。

这时只需考虑一个序列，在某根节点处被截成两段，且统计最大值。

考虑在 $m$ 处被截断，截成 ${a_1,a_2,\cdots,a_m}$ 和 ${a_{m+1},a_{m+2},\cdots,a_k}$。

考虑如何用两段的信息合并成一段的，有：

$$\sum_{i=1}^ki\times a_i\=\sum_{i=1}^mi\times a_i+\sum_{i=m+1}^{k}i\times a_i\=\sum_{i=1}^mi\times a_i+\sum_{i=m+1}^k(i-m)\times a_i+m\sum_{i=m+1}^ka_i$$

对于某一序列 ${a_1,a_2,\cdots,a_k}$，设 $s=\sum_{i=1}^ki\times a_i,v=\sum_{i=1}^ka_i$。

那么两段序列的信息合成一段就是：$s_1+s_2+m_1v_2$。

考虑点分治时，需要从某两棵不同的子树中统计答案。

如图所示：

G1

将子树按顺序从左到右排成一列，假设枚举到某棵子树，不妨设序列的前半部分出现在后面的子树中（否则反过来再做一遍即可）。

那么如果把后半部分的 $(s_2,v_2)$ 看做插入；把前半部分看做询问 $s_2+m_1v_2$ 的最大值，最后加上 $s_1$ 的值。显然 $s_2+m_1v_2$ 是一个直线的形式。将 $m_1$ 看作 $x$，$v_2$ 为斜率 $k$，$s_2$ 为纵截距 $b$。

也就是求若干条线段在 $x=m_1$ 处的最大值。

李超线段树，插入整个线段维护即可。

点分治时间复杂度 $O(n\log n)$，李超线段树复杂度 $O(\log n)$，总复杂度 $O(n\log ^2n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&(-(x)))
#define bit(x,i) (((x)>>(i))&1)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=150010;
struct line{
	ll k,b;
	ll f(int x){return k*x+b;}
};
namespace SGT{
	#define lc (u<<1)
	#define rc (u<<1|1)
	#define ls lc,l,mid
	#define rs rc,mid+1,r
	line mx[N<<2];
	void init(int u,int l,int r)
	{
		mx[u].k=mx[u].b=0;
		if(l==r) return;
		int mid=l+r>>1;
		init(ls); init(rs);
	}
	ll ask(int u,int l,int r,int x)
	{
		if(l==r) return mx[u].f(x);
		int mid=l+r>>1;
		return max(mx[u].f(x),(x<=mid)?ask(ls,x):ask(rs,x));
	}
	void add(int u,int l,int r,line A)
	{
		if(mx[u].f(l)<=A.f(l)&&mx[u].f(r)<=A.f(r)) {mx[u]=A; return;}
		if(mx[u].f(l)>=A.f(l)&&mx[u].f(r)>=A.f(r)) return;
		int mid=l+r>>1;
		if(mx[u].f(mid)<A.f(mid)) swap(mx[u],A);
		if(A.k<mx[u].k) add(ls,A);
		else add(rs,A);
	}
}

int n;
ll val[N],ans;
vector<int> adj[N];
int siz[N],mxsiz[N],rt;
int dep[N],fa[N],cnt;
int st[N],len[N],from[N],top;
ll sum[N],val1[N],val2[N];
bool vis[N];
inline void add(int x,int y)
{
	adj[x].pb(y); adj[y].pb(x);
}
void getroot(int u,int cnt)
{
	siz[u]=1; mxsiz[u]=0;
	for(auto v:adj[u])
		if(!vis[v]&&v!=fa[u])
		{
			fa[v]=u;
			getroot(v,cnt);
			siz[u]+=siz[v];
			mxsiz[u]=max(mxsiz[u],siz[v]);
		}
	mxsiz[u]=max(mxsiz[u],cnt-siz[u]);
	if(mxsiz[rt]>mxsiz[u]) rt=u;
}
void dfs(int u,ll v1,ll v2,ll s,int id)
{
	dep[u]=dep[fa[u]]+1;
	siz[u]=1;
	bool flag=0;
	for(auto v:adj[u])
		if(!vis[v]&&v!=fa[u])
		{
			fa[v]=u; flag=1;
			dfs(v,v1+s+val[v],v2+1ll*dep[u]*val[v],s+val[v],id);
			siz[u]+=siz[v];
		}
	if(!flag)
	{
		st[++top]=u; cnt=max(cnt,dep[u]);
		len[top]=dep[u]; val1[top]=v1; val2[top]=v2; from[top]=id; sum[top]=s;
	}
}
inline void calc(int u)
{
	st[top=0]=-1; dep[u]=1; cnt=0;
	for(auto v:adj[u]) if(!vis[v]) fa[v]=u,dfs(v,0ll+val[u]*2+val[v],val[v],val[v]+val[u],v);
	fo(i,1,top) sum[i]-=val[u],ans=max(ans,val1[i]),ans=max(ans,val2[i]+sum[i]+val[u]);
	st[top+1]=-1;
	SGT::init(1,1,cnt);
	for(int i=1,j;i<=top;i=j)
	{
		for(j=i;from[i]==from[j];j++) ans=max(ans,SGT::ask(1,1,cnt,len[j])+val1[j]);
		for(j=i;from[i]==from[j];j++) SGT::add(1,1,cnt,(line){sum[j],val2[j]});
	}
	SGT::init(1,1,cnt);
	for(int i=top,j;i;i=j)
	{
		for(j=i;from[i]==from[j];j--) ans=max(ans,SGT::ask(1,1,cnt,len[j])+val1[j]);
		for(j=i;from[i]==from[j];j--) SGT::add(1,1,cnt,(line){sum[j],val2[j]});
	}
}
void solve(int u)
{
	vis[u]=1;
	calc(u);
	for(auto v:adj[u])
	{
		if(vis[v]||siz[v]==1) continue;
		fa[v]=0; rt=0; getroot(v,siz[v]); solve(rt);
	}
}

int main()
{
	n=read();
	fo(i,2,n) add(read(),read());
	fo(i,1,n) val[i]=read();
	mxsiz[rt=0]=(int)1e9;
	getroot(1,n);
	solve(rt);
	printf("%lld",ans);
	return 0;
}