Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define f first
- #define s second
- typedef long long lli;
- typedef pair<int, int> pii;
- typedef pair<lli, lli> pll;
- const int N = 1e5 + 5;
- const int P0 = 1e4 + 7;
- const int P2 = 1e9 + 7;
- const int P1 = 98765431;
- vector<int> adj[N];
- int nVertex, rnk[N];
- void DFS(int u, int p, int depth){
- rnk[u] = depth;
- for(int v : adj[u]){
- if(v == p){
- continue;
- }
- DFS(v, u, depth + 1);
- }
- }
- int findFarthest(int r){
- DFS(r, 0, 1);
- int mx = 0;
- int rt = 0;
- for(int u = 1; u <= nVertex; ++u){
- if(rnk[u] > mx){
- mx = rnk[u];
- rt = u;
- }
- }
- return rt;
- }
- vector<int> sq;
- pii DFSCenter(int u, int p, int ed){
- sq.push_back(u);
- if(u == ed){
- int m = ((int)sq.size() - 1) / 2;
- if(sq.size() % 2 == 0){
- return pii(sq[m], sq[m + 1]);
- }
- return pii(sq[m], 0);
- }
- for(int v : adj[u]){
- if(v == p){
- continue;
- }
- pii nxt = DFSCenter(v, u, ed);
- if(nxt.f != 0){
- return nxt;
- }
- }
- sq.pop_back();
- return pii(0, 0);
- }
- lli treeIso(int u, int p){
- vector<lli> chd;
- for(int v : adj[u]){
- if(v == p){
- continue;
- }
- chd.push_back(treeIso(v, u));
- }
- sort(chd.begin(), chd.end());
- lli rt = P0;
- for(lli x : chd){
- rt = ((rt * P1) ^ x) % P2;
- }
- return rt;
- }
- pll hshTree(){
- for(int i = 1; i <= nVertex; ++i){
- adj[i].clear();
- }
- for(int i = 1; i < nVertex; ++i){
- int u, v;
- scanf("%d%d", &u, &v);
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- int u = findFarthest(1);
- int v = findFarthest(u);
- sq.clear();
- pii ct = DFSCenter(u, 0, v);
- if(ct.s == 0){
- return pll(treeIso(ct.f, 0), 0);
- } else {
- return pll(treeIso(ct.f, 0), treeIso(ct.s, 0));
- }
- }
- int main(){
- int Q;
- scanf("%d", &Q);
- while(Q--){
- scanf("%d", &nVertex);
- pll a = hshTree();
- pll b = hshTree();
- bool isSame = false;
- if(a.s == 0 && b.s == 0){
- isSame = (a.f == b.f);
- } else if(a.s != 0 && b.s != 0){
- isSame = (a.f == b.f) || (a.s == b.f);
- }
- if(isSame){
- cout << "YES\n";
- } else {
- cout << "NO\n";
- }
- }
- return 0;
- }
Advertisement
RAW Paste Data
Copied
Advertisement