1 solutions

  • 1
    @ 2025-9-9 20:14:00
    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<map>
    using namespace std;
    const int NR=1e5+10,P=1e5+7,A=1; //A是单点点权
    unsigned long long p[NR];
    struct Tree
    {
    	vector<int> e[NR];
    	int n,sz[NR];
    	unsigned long long g[NR],h[NR];
    	void dfs(const int x,const int fa) //求sz[i]、h[i]
    	{
    		sz[x]=1;
    		h[x]=A;
    		int i;
    		for(i=0;i<e[x].size();i++)
    		{
    			int y=e[x][i];
    			if(y!=fa)
    			{
    				dfs(y,x);
    				sz[x]+=sz[y];
    				h[x]+=h[y]*p[sz[y]];
    			}
    		}
    		return;
    	}
    	void cal(const int x,const int fa)
    	{
    		int i;
    		for(i=0;i<e[x].size();i++)
    		{
    			int y=e[x][i];
    			if(y!=fa)
    			{
    				g[y]=h[y]+(g[x]-h[y]*p[sz[y]])*p[n-sz[y]];
    				cal(y,x);
    			}
    		}
    		return;
    	}
    };
    map<unsigned long long,bool> mp;
    Tree a,b;
    int main()
    {
    	int i;
    	cin>>a.n;
    	b.n=a.n+1;
    	p[0]=1;
    	for(i=1;i<=b.n;i++) p[i]=p[i-1]*P; //要求到n+1
    	// for(i=1;i<=b.n;i++) cout<<p[i]<<" ";
    	// cout<<endl;
    	for(i=1;i<a.n;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		a.e[x].push_back(y);
    		a.e[y].push_back(x);
    	}
    	for(i=1;i<b.n;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		b.e[x].push_back(y);
    		b.e[y].push_back(x);
    	}
    	//先求出A的n个hash值
    	a.dfs(1,0);
    	a.g[1]=a.h[1];
    	a.cal(1,0);
    	// for(i=1;i<=a.n;i++) cout<<a.g[i]<<" ";
    	// cout<<endl;
    	//再求出B的n+1个hash值
    	b.dfs(1,0);
    	b.g[1]=b.h[1];
    	b.cal(1,0);
    	for(i=1;i<=a.n;i++) mp[a.g[i]]=true;
    	for(i=1;i<=b.n;i++)
    	{
    		if(b.e[i].size()!=1) continue; //i不是叶子就跳过
    		int y=b.e[i][0]; //找到i点唯一邻居
    		if(mp[b.g[y]-A*P]) //y作为根然后去掉i点
    		{
    			cout<<i;
    			break;
    		}
    	}
    	return 0;
    }
    
    
    • 1

    Information

    ID
    3272
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    6
    Tags
    # Submissions
    1
    Accepted
    1
    Uploaded By