A | B | C | D | Sum | Rank |
---|---|---|---|---|---|
0 | 0 | 10 | - | 10 | 16/18 |
A. 灯若辰星
B. 彻天之火
求出每条边被哪些路径经过,记为 \(s_i\),出现次数最多的 \(s_i\) 的出现次数为 \(S\),答案即为 \(n-1-S\)。异或哈希即可。
Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define il inline
#define ull unsigned ll
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,m;
ull a[maxn];
vector<int> e[maxn];
mt19937_64 rd(time(0));
__gnu_pbds::gp_hash_table<ull,int> cnt;
il void dfs(int u,int fa){for(int v:e[u]){if(v==fa){continue;}dfs(v,u);a[u]^=a[v];}if(u>1){cnt[a[u]]++;}
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1,u,v;i<n;i++){cin>>u>>v;e[u].pb(v),e[v].pb(u);}for(int i=1,u,v;i<=m;i++){cin>>u>>v;ull x=0;while(!x){x=rd();}a[u]^=x,a[v]^=x;}dfs(1,0);int ans=0;for(auto x:cnt){ans=max(ans,x.second);}cout<<n-1-ans;return 0;
}
}
int main(){return asbt::main();}