[原创]SUDT 3926 bLue的二叉树 [KMP or hash]【思维】

2017-06-05 01:35:52 Tabris_ 阅读数：360

博客爬取于2020-06-14 22:40:08
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72863523

题目链接:http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2176/pid/3926.html
——————————————————————————————————————
bLue的二叉树
Time Limit: 3000MS Memory Limit: 65536KB
Submit Statistic
Problem Description

Keke 是一个喜爱种树的人，他对各种树都有很深的研究。
MLE 听说 bLue 种了一些新品种的树，就想邀请 Keke 去围观一下。
PBH 在暗中把这一切尽收眼底，作为资深植树行家，他虽不屑，但也决定和他们一起去看一看。
于是，大家便一起到了 bLue 家去看树。
bLue 有两棵二叉树，分别有 n 和 m 个节点，编号分别为 1-n 和 1-m，每个节点都有一个权值，bLue 想知道第一棵树的所有子树中与第二棵树完全相同的个数(不考虑节点编号)。
Input

输入数据有多组，组数不超过 150，到 EOF 结束。
每组第一行有两个整数 n (0 < n <= 1e5)和 m (0 < m <= 1e5)，表示第一棵树和第二棵树的节点个数；
接下来 n 行，表示第一棵树：第 i (0 < i <= n) 行有 3 个整数，w[i] (0 < w[i] <= 10), lc[i], rc[i] (0 < lc[i], rc[i] <= n)，分别表示节点 i 的权值，该节点的左孩子编号和右孩子编号，若某个孩子不存在，则为 0 (数据保证每棵树都是合法的有根二叉树)；
接下来 m 行，表示第二棵树：格式同第一棵树；
保证：树的最大深度不会超过 10000。数据量比较大，请用 scanf 读入！
Output

对于每组数据，输出一行一个整数 num，表示第一棵树的所有子树中与第二棵树完全相同的个数。
Example Input

7 4
1 6 3
2 0 4
1 7 0
3 0 0
1 2 1
2 0 0
2 0 0
2 0 0
1 4 0
1 1 2
2 0 0
3 3
1 0 0
2 1 3
3 0 0
1 0 3
2 1 0
3 0 0
Example Output

1
0
Hint

Author

不得不放弃、
——————————————————————————————————————
首先确定的是严格确定 二叉树的左子树和左子树对 上右子树和右子树对上才行

对于子树问题考虑dfs序
对于一个dfs序,区间内的东西都是子树的,那么对于两个完全一样的子树.遍历出来的区间也是一模一样的.

但是为了避免有多个子树遍出结果一样的,我们只需把空节点当作一个不一样的权值加入到树中,这样既能确保区间序列一样,同时又不会冲突.

最后对两个dfs序KMP即能求解

其实这题是能够hash做的 ，最开始我也在想hash的方法，但是想不到怎么处理左右儿子的左/右儿子到底在那，所以不太行，，== 现在想到对dfs序后他的位置l的x^l的系数 感觉很可行啊 ，同时也要做dfs==！ 其实还是字符串hash了，，，，，

附本题两份KMP+hash代码
——————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N    = 1e5+10;
const int MOD  = 1e9+7;

int sum;
LL read(){
    LL x=0;char ch=getchar();
    while('0'>ch||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';sum++;ch=getchar();}
    return x;
}
/******************************************/

int n,m;
int a[N][3],b[N][3],c[N<<1],d[N<<1],lc,ld;

void dfs1(int rt){
    c[lc++]=a[rt][0];//printf("%d ",a[rt][0]);
    if(rt==0) return;
    dfs1(a[rt][1]);
    dfs1(a[rt][2]);
}

void dfs2(int rt){
    d[ld++]=b[rt][0];//printf("%d ",b[rt][0]);
    if(rt==0) return;
    dfs2(b[rt][1]);
    dfs2(b[rt][2]);
}
int Next[N<<1];//Next[i] 表示从[0~i]中最长公共前缀的长.
void get_next(int *s,int len){
    for(int i=0,j=-1;i<=len;++i,++j){
        Next[i]=j;
        while(j>=0&&s[i]!=s[j]) j = Next[j];
    }
//    for(int i=0;i<=len;i++) printf("%d%c",Next[i],(i==len)?'\n':' ');
}
//在串s上找sz
int KMP (int *s,int len,int *sz,int l){
    int i=0,j=0,cnt=0;
    while(i<len/*&&j<l*/){
        if(s[i]==sz[j])  i++,j++;
        else{
            if(0==j)  i++;
            else      j=Next[j];
        }
        if(j==l) cnt++;
    }
//   return (j==l)?(i-l+1):-1; //找第一次出现的位置
    return cnt; //找出现的个数
}
bool visa[N],visb[N];
int main(){
    while(~scanf("%d%d",&n,&m)){
        lc=ld=0;
        for(int i=1;i<=n;i++)  a[i][0]=read(),a[i][1]=read(),a[i][2]=read(),visa[a[i][1]]=visa[a[i][2]]=1;
        for(int i=1;i<=m;i++)  b[i][0]=read(),b[i][1]=read(),b[i][2]=read(),visb[b[i][1]]=visb[b[i][2]]=1;
        for(int i=1;i<=n;i++)  if(visa[i]==0){dfs1(i);break;}//puts("");
        for(int i=1;i<=m;i++)  if(visb[i]==0){dfs2(i);break;}//puts("");

        get_next(d,ld);
        printf("%d\n",KMP(c,lc,d,ld));
        for(int i=1;i<=n;i++) visa[i]=0;
        for(int i=1;i<=m;i++) visb[i]=0;
    }
    return 0;
}


/***************************************************
User name: tabris
Result: Accepted
Take time: 872ms
Take Memory: 596KB
Submit time: 2017-06-05 00:39:32
****************************************************/

# include <bits/stdc++.h>
typedef unsigned long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N    = 1e5+10;
const int MOD  = 1e9+7;

int sum;
LL read(){
    LL x=0;char ch=getchar();
    while('0'>ch||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';sum++;ch=getchar();}
    return x;
}
/******************************************/

int n,m,ans,lc,ld;
int a[N][3],b[N][3];//,lb[N],rb[N];
LL c[N<<1],x,h,tota,totb;

void dfs1(int rt){
    ++lc;
    c[lc]=a[rt][0]*x;x*=h;
    if(rt==0) return;
    dfs1(a[rt][1]);
    dfs1(a[rt][2]);
}

void dfs2(int rt){
    ++ld;
    totb+=b[rt][0]*x;x*=h;
    if(rt==0) return;
    dfs2(b[rt][1]);
    dfs2(b[rt][2]);
}

bool visa[N],visb[N];
int main(){
    a[0][0]=b[0][0]=101;h=27;c[0]=0;
    while(~scanf("%d%d",&n,&m)){
        lc=ld=0;ans=0;tota=totb=0;
        for(int i=1;i<=n;i++)  a[i][0]=read(),a[i][1]=read(),a[i][2]=read(),visa[a[i][1]]=visa[a[i][2]]=1;
        for(int i=1;i<=m;i++)  b[i][0]=read(),b[i][1]=read(),b[i][2]=read(),visb[b[i][1]]=visb[b[i][2]]=1;
        x=1;for(int i=1;i<=n;i++)  if(visa[i]==0){dfs1(i);break;}//puts("");
        x=1;for(int i=1;i<=m;i++)  if(visb[i]==0){dfs2(i);break;}//puts("");

        for(int i=1;i<ld;i++) tota+=c[i];
        for(int i=ld;i<=lc;i++){
            tota-=c[i-ld],tota+=c[i];
            if(tota==totb) ans++;
            totb*=h;
        }

        printf("%d\n",ans);
        for(int i=1;i<=n;i++) visa[i]=0;
        for(int i=1;i<=m;i++) visb[i]=0;
    }
    return 0;
}




/***************************************************
User name: tabris
Result: Accepted
Take time: 884ms
Take Memory: 2244KB
Submit time: 2017-06-05 01:34:54
****************************************************/