wordpress建站行吗,dw 网页设计与制作教程,成都网站优化排名,网站建设后期维护方案题干#xff1a;
JYY有两棵树A和B#xff1a;树A有N个点#xff0c;编号为1到N#xff1b;树B有N1个点#xff0c;编号为1到N1。JYY知道树B恰好是由树A加上一个叶
节点#xff0c;然后将节点的编号打乱后得到的。他想知道#xff0c;这个多余的叶子到底是树B中的哪一个…题干
JYY有两棵树A和B树A有N个点编号为1到N树B有N1个点编号为1到N1。JYY知道树B恰好是由树A加上一个叶
节点然后将节点的编号打乱后得到的。他想知道这个多余的叶子到底是树B中的哪一个叶节点呢 Input
输入一行包含一个正整数N。
接下来N-1行描述树A每行包含两个整数表示树A中的一条边
接下来N行描述树B每行包含两个整数表示树B中的一条边。
1≤N≤10^5 Output
输出一行一个整数表示树B中相比树A多余的那个叶子的编号。如果有多个符合要求的叶子输出B中编号最小的
那一个的编号 Sample Input
5 1 2 2 3 1 4 1 5 1 2 2 3 3 4 4 5 3 6
Sample Output
1
Hint
解题报告
哈希规则子树u的哈希值由它的每一个子树vi的哈希值得来首先将所有f(v)排个序防止顺序不同造成影响然后 W是事先选取的一个位权MOD是模数size(u)是子树u的大小。
这样DFS一遍可求出以1号节点为根时所有子树的哈希值f(u)。
但是这是无根树我们想求出以任意节点为根时整棵树的哈希值。
设fa[u]以1为根时u的父亲则上面的f(u)也是以fa[u]为根时子树u的哈希值。
再求一个g(u)表示以u为根时子树fa[u]的哈希值。这个g(u)怎么求呢再DFS一遍对于每个节点g(u)由g(fa[u])以及u的每个兄弟vi的f(vi)得来。但是直接暴力枚举的话在菊花图上是O(n^2)的那怎么办呢
对于每个节点u维护一个数组存储它所有儿子的哈希值f(v)如果有父亲则g(u)也在里面把这个数组排好序求出每个前缀的哈希值和每个后缀的哈希值。这时以u为根时整棵树的哈希值就是整个数组的哈希值再乘上子树大小n。
此时求每个儿子v的g(v)就是从那个数组中间去掉f(v)后的哈希值二分查找后把前缀哈希值和后缀哈希值拼起来就可以得到。记得乘上v为根时uu的size即n−size(v)。
这样就求出以每个节点为根的哈希值了。
把A的所有哈希值存到一个set里然后枚举B的每个度为1的点u求出以u为根它的唯一子树v的哈希值如果set里有这个值u就是所求的点之一。部分内容参考自链接
首先明确一个问题以u为根节点的树的Hash值树的大小 * 子树Hash值的带权和 % MOD也就是说这个根节点是以子树大小的身份参与到其中的。也就是HASH[u]其实重头戏在于u的孩子节点而u在其中的作用只是size那一部分权重而已其他的都与他无关。这是在做树的问题的时候和其他问题不一样的一点也是比较有特色的一点。
g[v]代表以v为根时子树u的Hash值。也就是以v为根节点的 部分哈希和那么g[v]由g[u]和v的一系列兄弟节点f[vi]带权得来。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
const ll MOD 2000020331;
//const ll MOD 2000004199; 用这个模数都没有问题
const ll seed 31;//
ll PW[MAX];
struct Edge {int v,ne;
} e[MAX];
int head[MAX],tot;
int n;
int deg[MAX];
bool isB;
void add(int u,int v) {if(isB) deg[u];e[tot].v v;e[tot].ne head[u]; head[u] tot;
}
int size[MAX],fa[MAX];
vectorll son[MAX],sl[MAX],sr[MAX];
ll f[MAX],g[MAX];
setll vis;
ll dfs1(int cur,int rt) {ll res 0;fa[cur] rt; son[cur].clear();//必须要清空 size[cur] 1;for(int i head[cur]; ~i; i e[i].ne) {int v e[i].v; if(v rt) continue;ll tmp dfs1(v,cur);son[cur].push_back(tmp);size[cur] size[v]; }if(son[cur].empty()) return f[cur] 1;//注意叶子结点的HASH值需要是1而不能是0也就是son数组中必须都是正数的HASH值。sort(son[cur].begin(),son[cur].end());int up son[cur].size();for(int i 0; iup; i) res (res * seed son[cur][i]) % MOD; return f[cur] size[cur] * res % MOD;
}
int ans;
void dfs2(int u) {if(fa[u]) {son[u].pb(g[u]);sort(son[u].begin(),son[u].end());}int up son[u].size();sl[u].resize(up);sl[u][0] son[u][0]; for(int i 1; iup; i) {//好像不太能把初始化合并进来 sl[u][i] (sl[u][i-1] * seed son[u][i])%MOD;}sr[u].resize(up);sr[u][up-1] son[u][up-1];for(int i up-2; i0; i--) sr[u][i] (sr[u][i1] son[u][i] * PW[up-i-1])%MOD; //其实不是求后缀的HASH值而是前缀HASH的后缀和所以要这么写 for(int i head[u]; ~i; i e[i].ne) {int v e[i].v;if(v fa[u]) continue;if(up 1) {g[v] 1; dfs2(v); break;}int p lower_bound(son[u].begin(),son[u].end(),f[v]) - son[u].begin();g[v] 0;if(p1 up) g[v] sr[u][p1];if(p-1 0) g[v] (g[v]sl[u][p-1]*PW[up-1-p])%MOD;g[v] g[v] * (n-size[v]) % MOD;if(isB deg[v] 1 vis.find(g[v]) ! vis.end()) ans min(ans, v);dfs2(v);}if(!isB) vis.insert(sl[u][up - 1] * n % MOD);
}
int main()
{PW[0] 1;for(int i 1; iMAX; i) PW[i] PW[i-1]*seed % MOD;cinn;memset(head,-1,sizeof head);for(int u,v,i 1; in; i) {cinuv;add(u,v);add(v,u);}dfs1(1,0); dfs2(1);tot0,isB1,n;memset(head,-1,sizeof head);for(int u,v,i 1; in; i) {cinuv;add(u,v);add(v,u);} dfs1(1,0);ans1e9;if(deg[1] 1 vis.find(f[e[head[1]].v]) ! vis.end()) ans 1;dfs2(1);printf(%d\n,ans); return 0 ;
}
另一种及其简单的Hash方式
我们只需要就可以了。
其中是每一个子树的hash值 这个函数和上一个函数一样支持换根那么就不限于找重心了 那第一颗树所有的hash值丢进set中第二颗树删除一个节点的hash值也可以用类似的方法弄出来。
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
//const ll MOD 2000020331;//这个模数在这个方法中可以直接扔掉了因为根本不是质数所以肯定要不了因为逆元的求法就不对。
const ll MOD 2000004199; //用这个模数都没有问题
const ll seed 13331;//可换 233,2333,23333对于第二个模数都可以过
ll INV;
struct Edge {int v,ne;
} e[MAX];
int head[MAX],tot;
int n;
void adde(int u,int v) {e[tot].v v;e[tot].ne head[u]; head[u] tot;
}
inline ll qpow(ll a,ll b) {ll res 1;while(b) {if(b1) res res * a % MOD;a a *a % MOD;b 1; }return res;
}
inline ll add(ll x,ll y) {return (xy)%MOD;}
inline ll mul(ll x,ll y) {return (x*y)%MOD;}
inline ll sub(ll x,ll y) {return (x-yMOD)%MOD;}
ll H[MAX];
int size[MAX],du[MAX];
void dfs(int cur,int fa) {H[cur] 1;size[cur] 1;for(int i head[cur]; ~i; i e[i].ne) {int v e[i].v;if(v fa) continue;dfs(v,cur);size[cur] add(size[cur],size[v]);H[cur] mul(H[cur],H[v]);}H[cur] add(H[cur],size[cur]);H[cur] mul(H[cur],seed);
}
setll ss;
bool isB;
void dfs1(int cur,int fa) {if(isB0) ss.insert(H[cur]);//必须要先插入因为根的情况。 ll Hall mul(H[cur],INV),Hres;Hall sub(Hall,n);for(int i head[cur]; ~i; i e[i].ne) {int v e[i].v;if(v fa) continue;Hresmul(Hall,qpow(H[v],MOD-2));Hresadd(Hres,n-size[v]); Hresmul(Hres,seed);//至此Hres代表除v的树的Hash值H[v]mul(H[v],INV); H[v]sub(H[v],size[v]);H[v]mul(H[v],Hres);H[v]add(H[v],n);H[v]mul(H[v],seed);dfs1(v,cur);}
}
int main()
{INV qpow(seed,MOD-2);cinn;tot0;memset(head,-1,sizeof head);for(int u,v,i 1; in; i) scanf(%d%d,u,v),adde(u,v),adde(v,u);dfs(1,0);dfs1(1,0);tot0;memset(head,-1,sizeof head);n;for(int u,v,i 1; in; i) {scanf(%d%d,u,v);du[u],du[v];adde(u,v);adde(v,u);}isB1;dfs(1,0);dfs1(1,0);for(int i 1; in; i) {if(du[i] 1) {ll Hres mul(H[i],INV);Hres sub(Hres,n);if(ss.find(Hres) ! ss.end()) {printf(%d\n,i);return 0 ;}}}return 0 ;
}
