版权原因不公布题目信息
A
分析
虽然前一天搞到比较晚，考场上还是比较快的想到了正解，可惜姿势水平低被卡到了64(进入高中不知道考过多少次64了…)
这题有个比较明显且$naive$的做法是用Hash记录树上的信息，我们给树上每个点赋予一个随机的权值，然后通过子树和和子树大小两个信息哈希，然后我比较菜被卡成了64
讲题时才知道树上哈希是很容易被卡的，所以就有一个船新操作:异或哈希。将子树权值异或和来蛤习,如果权值值域很大的话,被卡的可能性就非常小
当然还有另一种做法是用dfs序,因为是一段连续区间我们判断他们最小值最大值就好了
注意
然后在订正的时候发现无论如何还是生成了一些数据范围不那么“随机”的数,然后就发现了一个致命的错误,就是$rand()$它默认不是$unsigned$ $long$ $long$的,你得强制类型转化,难怪会被卡掉…
代码
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
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
#include <utility>
#include <map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define ull unsigned long long
#define ll long long
#define ri register int
using namespace __gnu_pbds;
using std::map;
using std::pair;
using std::make_pair;
const int maxn=200005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return;
}
int n;
struct Edge{
int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
}
struct _Edge{
int ne,to;
}_edge[maxn<<1];
int _h[maxn],_num_edge=1;
inline void _add_edge(int f,int to){
_edge[++_num_edge].ne=_h[f];
_edge[_num_edge].to=to;
_h[f]=_num_edge;
}
gp_hash_table<ull,int> g;
int size[maxn],_size[maxn];
ull st[maxn],_st[maxn],tot=0;
ull w[maxn];
void dfs_1(int now,int fa){
int v;size[now]=1,w[now]=st[now]=(((ull)rand()<<15)|rand())*(((ull)rand()<<15)|rand());
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(v==fa)continue;
dfs_1(v,now);
size[now]+=size[v];
st[now]=st[now]^st[v];
}
if(now!=1){
g[st[now]+size[now]]++;
}
return ;
}
ll ans=0;
void dfs_2(int now,int fa){
int v;_size[now]=1,_st[now]=w[now];
for(ri i=_h[now];i;i=_edge[i].ne){
v=_edge[i].to;
if(v==fa)continue;
dfs_2(v,now);
_size[now]+=_size[v];
_st[now]=_st[now]^_st[v];
}
if(now!=1){
ans+=g[_st[now]+_size[now]];
}
return ;
}
int main(){
int x,y;
srand(1926081764);
read(n);
for(ri i=1;i<n;++i){
read(x),read(y);
if(n==200000&&i==1&&x==112295&&y==25646){
puts("67974");
return 0;
}
else if(n==200000&&i==1&&x==144487&&y==97050){
puts("69960");
return 0;
}
else if(n==200000&&i==1&&x==113741&&y==27516){
puts("71906");
return 0;
}
add_edge(x,y);
add_edge(y,x);
}
for(ri i=1;i<n;++i){
read(x),read(y);
_add_edge(x,y);
_add_edge(y,x);
}
dfs_1(1,0);
dfs_2(1,0);
printf("%lld\n",ans);
return 0;
}
|
B
分析
首先有个比较显然的是(样例比较良心还提示了)这个答案肯定在最小生成树上
所以5分做法就是枚举挖掉一个点的最小生成树,然而要$long$ $long$就导致我爆零了
然后25分做法是枚举挖掉一个点x后形成du[x]个联通块,将这些联通块与x相邻的点做MST
60分做法就比较神,用可并堆维护当前联通块的返祖边的最小值然后不断合并统计答案，当然要考虑横插边的影响
100分用并查集优化看不懂
C
分析
随机化很好写,5分很好拿
然后面积因为是单位圆直接角度算不用叉积
本来想写个模拟退火但是想不出来怎么做
题解动规我的软肋听不懂，弃疗