赛时rank17,T1 18,T2 50,T3 0,T4 40
博弈
异或hash。
当crying必胜时，一定为有一个权值出现次数为奇数，证明是显然的。
然后就可以考虑异或了。
将每个相同的权值换成一个很大的随机权值，然后在树上异或。两个点之间的路径为\(dist_x\oplus dist_y \oplus dist_{lca} \oplus dist_{lca} = dist_x \oplus dist_y\)
不合法的时候当且仅当\(dist_x\oplus dist_y=0\)，将不合法的记录下来即可。
建议将权值换成大一点的，减少错误概率。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
struct EDGE{int to,next;ll w;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v,ll w){
edge[++cnt] = {v,head[u],w};
head[u] = cnt;
}
int n,u[N],v[N];
ll w[N];
ll dist[N],rd[N];
unordered_map<ll,int> mp;
void dfs(int x,int fa){
mp[dist[x]]++;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == fa) continue;
dist[y] = dist[x]^edge[i].w;
dfs(y,x);
}
}
inline void solve(){
mt19937_64 rnd((ull)(new char));
int T;cin>>T;
while(T--){
cin>>n;
vector<int> num;
for(int i = 1;i < n; ++i) cin>>u[i]>>v[i]>>w[i],num.emplace_back(w[i]);
cnt = 0;
for(int i = 1;i <= n; ++i) head[i] = 0;
unordered_map<ll,int> ().swap(mp);
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
for(int i = 1;i <= n; ++i) rd[i] = rnd();
for(int i = 1;i < n; ++i)
w[i] = lower_bound(num.begin(),num.end(),w[i]) - num.begin() + 1;
for(int i = 1;i < n; ++i) w[i] = rd[w[i]];
for(int i = 1;i < n; ++i) add(u[i],v[i],w[i]),add(v[i],u[i],w[i]);
dfs(1,0);
ll ans = 0;
for(auto i:mp) ans += 1ll*i.second*(i.second-1);
cout<<(1ll*n*(n-1)-ans)/2<<'\n';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
跳跃
一个没有看懂的dp
大陆
神奇的构造题，神(晶晶晶)说是树分块前置知识，膜拜神~~~~~~~~~
构造方法 :
-
dfs整棵树，对于dfs到的一个节点，将其符合条件的子节点分块，将未被分块的返回上一层，这个用一个栈维护即可。
-
将未被分块的子节点添加到现集合\(S\)中，如果\(|S|\ge B\)那么就将该节点设为省会，然后清空\(S\)
-
处理完所有的子树后，再将当前节点加入\(S\)中，返回上一层。
-
如果dfs完后还有节点，那么以根节点为省会，并入一个块即可。
证明 :
考虑到对于每个节点，它上传回去的节点最多为\(B-1\)，所以每次在枚举到的点的集合大小最大为\(B-1+1=B\)。
又由于返回的集合最大为\(B\)，一个子树的贡献最多为\(B-1\)，所以一个块最多为\(2\times B-1\)，符合条件。
最后的剩余节点最多为\(B\)，加上原来的节点最多为\(3\times b-1\)，符合条件
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e3 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
int n,m,tot,rt[N],bel[N],sta[N],top;
void dfs(int x,int fa){
int cur = top;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == fa) continue;
dfs(y,x);
if(top - cur >= m){
rt[++tot] = x;
while(top > cur) bel[sta[top--]] = tot;
}
}
sta[++top] = x;
}
inline void solve(){
cin>>n>>m;
for(int i = 1,u,v;i < n; ++i) cin>>u>>v,add(u,v),add(v,u);
dfs(1,0);
if(!tot) rt[++tot] = 1;
while(top) bel[sta[top--]] = tot;
cout<<tot<<'\n';
for(int i = 1;i <= n; ++i) cout<<bel[i]<<' ';
cout<<'\n';
for(int i = 1;i <= tot; ++i) cout<<rt[i]<<' ';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
排列
神奇的\(fhq\_treap\)题，不会。
