分类目录归档：树

洛谷 P3367 【模板】并查集

发表评论

明明记得之前应该有并查集的板子在博客里？怎么找不到了？？

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int father[10005];
int _find(int num) {
    if (father[num] == -1)return num;
    else return father[num] = _find(father[num]);
}
void _union(int v1, int v2) {
    if (_find(v1) == _find(v2))return;
    father[_find(v2)] = v1;
}
int n, m;
int main(){
    memset(father, -1, sizeof(father));
    cin >> n >> m;
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1)_union(x, y);
        else cout << (_find(x) == _find(y) ? 'Y' : 'N') << endl;
    }
}

洛谷 P1030 求先序排列

发表评论

这类型的题（给中序和前后任一个，让求另外一个的）已经做了不下3、4遍了。。
再贴出来，代码风格可能会不大一样。。。应该是相比之前的有很多改进的。。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<deque>
#include<map>
#include<cstring>
using namespace std;

struct node {
    char l, r;
    node() {
        l = r = '*';
    }
    node(char l1, char r1) {
        l = l1;
        r = r1;
    }
};
map<char, node> dic;

string in, post;

inline int searchInTraversal(char v, int s, int e) {
    for (int i = s; i <= e; i++)if (in[i] == v)return i;
    return -1;
}
char buildTree(int is, int ie,int ps,int pe) {
    char father = post[pe];
    if (is == ie && ps == pe) {
        dic[father] = node();
        return father;
    }
    if (is > ie || ps > pe) {
        return '*';
    }
    int posOfF = searchInTraversal(father, is, ie);
    int lTreeLen = posOfF - is;
    char l = buildTree(is, posOfF - 1, ps, ps + lTreeLen - 1);
    char r = buildTree(posOfF + 1, ie, ps + lTreeLen, pe - 1);
    dic[father] = node(l, r);
    return father;
}
void preTraversal(char node) {
    if (node == '*')return;
    cout << node;
    preTraversal(dic[node].l);
    preTraversal(dic[node].r);
}

int main() {
    cin >> in >> post;
    char f=buildTree(0, in.length() - 1, 0, post.length() - 1);
    preTraversal(f);
}

洛谷 加分二叉树

发表评论

题号：P1040
很有意义，想了不短时间，和一位群里的同学讨论了一下：代码如下：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

洛谷 【模板】线段树 1

发表评论

题号：P3372

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
#include<vector>
#include<list>
#include<stack>
#include<queue>
struct node{
    long long value;
    long long lazymark;
}segment_tree[400005];
void build(int root, long long * arr, int start, int end){
    segment_tree[root].lazymark = 0;
    if (start == end){
        segment_tree[root].value = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(root * 2 + 1, arr, start, mid);
    build(root * 2 + 2, arr, mid + 1, end);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}
void pushdown(int root,int start,int end){
    if (segment_tree[root].lazymark == 0)return;
    int mid = (start + end) / 2;
    segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1);
    segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid);
    segment_tree[root].lazymark = 0;
}
long long query(int root, int cstart, int cend, int qstart, int qend){
    if (qstart > cend || qend < cstart)return 0;
    if (qstart <= cstart&&cend <= qend)return segment_tree[root].value;
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend);
}
void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){
    if (cend < ustart || uend < cstart)return;
    if (ustart <= cstart&&cend <= uend){
        segment_tree[root].value += addvalue*(cend - cstart + 1);
        segment_tree[root].lazymark += addvalue;
        return;
    }
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue);
    update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}

using namespace std;
int n, m;
long long arr[100005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    build(1, arr, 1, n);
    while (m--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            long long z;
            cin >> x >> y >> z;
            update(1, 1, n, x, y, z);
        }
        else{//op==2
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }
}

zcysky标程：

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
#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
using namespace std;
int a[N],n,m;
inline ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
ll sumv[N<<2],addv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void pushdown(int o,int l,int r){
    if(!addv[o])return;
    ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1;
    addv[lson]+=tag;addv[rson]+=tag;
    sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid);
}
inline void build(int o,int l,int r){
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
inline void optadd(int o,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;}
    int mid=(l+r)>>1;pushdown(o,l,r);
    if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
    if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return sumv[o];
    pushdown(o,l,r);
    int mid=(l+r)>>1;ll ans=0;
    if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            ll k=read();optadd(1,1,n,l,r,k);
        }
        else printf("%lld\n",querysum(1,1,n,l,r));
    }
}

20180816更新：

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
#include<iostream>
using namespace std;

struct segmentTree{
    typedef long long ll;
    const static ll MAX=100000;
    ll v[4*MAX],m[4*MAX];
    inline static ll lson(ll r){return r*2+1;}
    inline static ll rson(ll r){return r*2+2;}
    void build(ll r,ll * a,ll s,ll e){
                m[r]=0;
                if(s==e){v[r]=a[s];return;}
                ll md=(s+e)>>1;
        build(lson(r),a,s,md);
        build(rson(r),a,md+1,e);
        v[r]=v[lson(r)]+v[rson(r)];
        }
    void pushDown(ll r,ll s,ll e){
        if(m[r]==0)return;
        ll md=(s+e)>>1;
        m[lson(r)]+=m[r];
        m[rson(r)]+=m[r];
        v[lson(r)]+=m[r]*(md-s+1);
        v[rson(r)]+=m[r]*(e-md);
        m[r]=0;
    }
    ll query(ll r,ll cs, ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r];
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)/2;
        return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe);
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){
        if(ce<us||ue<cs)return;
        if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;}
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv);
        update(rson(r),cmd+1,ce,us,ue,addv);
        v[r]=v[lson(r)]+v[rson(r)];
    }
}ST;
typedef long long ll;
ll n,m;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)<<endl;
        }
    }
}

洛谷/USACO 美国血统 American Heritage

发表评论

洛谷题号：P1827
做过二百遍的二叉树重构了，老套路：

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
char in[30],pre[30];
#define NULL 0
struct node{
    char value;
    node * left;
    node * right;
    node(){
        value = '\0';
        left = NULL;
        right = NULL;
    }
};
int find_in(int in_s, int in_e, char node){
    for (int i = in_s; i <= in_e; i++){
        if (in[i] == node)return i;
    }
    assert(0);
    return -1;
}
void BuildTree(int in_s, int in_e, int pre_s, int pre_e, node * root){
    if (in_s == in_e&&pre_s == pre_e){
        root->value = pre[pre_s];
        return;
    }
    if (in_s > in_e || pre_s > pre_e){
        return;
    }
    root->value = pre[pre_s];
    int pos_in = find_in(in_s, in_e, pre[pre_s]);
    root->left = new node;
    BuildTree(in_s, pos_in - 1, pre_s + 1, pre_s + pos_in - in_s, root->left);
    root->right = new node;
    BuildTree(pos_in + 1, in_e, pre_s + pos_in - in_s + 1, pre_e, root->right);
}
void postorder_traversal(node * ptr){
    if (ptr->left != NULL)postorder_traversal(ptr->left);
    if (ptr->right != NULL)postorder_traversal(ptr->right);
    if (ptr->value != '\0')cout << ptr->value;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> in+1 >> pre+1;
    int len = 1;
    while (in[len])len++;
    len--;
    node * root = new node;
    BuildTree(1, len, 1, len, root);
    postorder_traversal(root);
    cout << endl;
}

洛谷 银河英雄传说

发表评论

题号：P1196
参见题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1196
结合源代码阅读才好……
推荐题解作者：作者: 超神火星人 更新时间: 2017-04-29 09:14

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
int father[30005],size[30005],front[30005];
using namespace std;
int sfind(int node){
    if (father[node] == -1)return node;
    int fn = sfind(father[node]);
    front[node] += front[father[node]];
    return father[node]=fn;
}
int main(){
    for (int i = 1; i <= 30000; i++){
        father[i] = -1;
        size[i] = 1;
        front[i] = 0;
    }
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--){
        char c;
        int rf1, rf2;
        cin >> c >> rf1 >> rf2;
        int fa1 = sfind(rf1);
        int fa2 = sfind(rf2);
        switch (c){
        case 'M':
            front[fa1] += size[fa2];
            father[fa1] = fa2;
            size[fa2] += size[fa1];
            size[fa1] = 0;
            break;
        case 'C':
            if (fa1 != fa2)cout << "-1" << endl;
            else cout << abs(front[rf1] - front[rf2])-1 << endl;
            break;
        }
    }
}

20180815更新：
重做了这道题，还是看的这个人的题解。。。。

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
#include<iostream>
using namespace std;
int t;
int father[30005],front[30005],num[30005];
int _find(int node){
    if(father[node]==0)return node;
    int fn=_find(father[node]);
    front[node]+=front[father[node]];
    return father[node]=fn;
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=1;i<=30000;i++)num[i]=1;
    cin>>t;
    while(t--){
        char op;
        int x,y;
        cin>>op>>x>>y;
        int fx=_find(x),fy=_find(y);
        if(op=='M'){
            front[fx]+=num[fy];
            father[fx]=fy;
            num[fy]+=num[fx];
            num[fx]=0;
        }else{
            if(fx!=fy)cout<<-1<<endl;
            else cout<<abs(front[x]-front[y])-1<<endl;
        }
    }  
}

发现越到后面就越感觉是在抄题解怎么办，想也想不出来。

洛谷 关押罪犯

发表评论

题号：1525
参见题解：作者: 超级范范 更新时间: 2017-07-23 17:05
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1525

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int father[40005];
struct s{
    int u, v, w;
    bool operator < (s & s1){
        return w>s1.w;
    }
}arr[100005];
int _find(int node){
    if (father[node] == -1)return node;
    return father[node] = _find(father[node]);
}
void merge(int x, int y){
    x = _find(x);
    y = _find(y);
    if (x != y)father[x] = y;
}
bool sameset(int x, int y){
    return _find(x) == _find(y);
}
int main(){
    memset(father, -1, sizeof(father));
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> arr[i].u >> arr[i].v >> arr[i].w;
    }
    sort(arr + 1, arr + m + 1);
    int maxw = 0;
    for (int i = 1; i <= m; i++){
        if (sameset(arr[i].u, arr[i].v)){
            if (arr[i].w > maxw){
                cout << arr[i].w;
                return 0;
            }
        }
        else{
            merge(arr[i].u, arr[i].v + n);
            merge(arr[i].v, arr[i].u + n);
        }
    }
    cout << 0;
}

20180814更新：除了并查集做法还有二分图做法，应该也很好做，不写了。
题解：https://www.luogu.org/blog/Kesdiael3/solution-p1525

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
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct p{
    int a,b,c;
    bool operator < (const p& p2) const{
        return c>p2.c;
    }
}ps[100005];
int father[40005];
int _find(int x){
    if(father[x]==0)return x;
    return father[x]=_find(father[x]);
}
bool _union(int x,int y){
    if(_find(x)==_find(y))return false;
    father[_find(x)]=_find(y);
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>ps[i].a>>ps[i].b>>ps[i].c;
    sort(ps+1,ps+m+1);
    for(int i=1;i<=m;i++){
        if(_find(ps[i].a)==_find(ps[i].b)){
            cout<<ps[i].c;
            return 0;
        }else{
            _union(ps[i].a,ps[i].b+n);
            _union(ps[i].b,ps[i].a+n);
        }
    }
    cout<<0;
}

计蒜客 NOIP模拟赛（一） D1T2

发表评论

原题：https://nanti.jisuanke.com/t/16446
北京市八十中的cjr说（特别感谢cjr提供思路，我进行了一下整理）：考虑每条边对答案的贡献：每条边肯定是一个父亲节点与一个儿子节点相连，该边对答案的贡献是size[i]*(n-size[i])*w，其中i为儿子节点，size[i]为该边的儿子节点所对应的子树大小（包括该儿子节点），w[i]为边权，n为总节点数。可以这样做是利用了乘法原理。想象一下，假设一棵有根树，要计算从Node:n到其它所有节点的最短距离：

该边必然要使用1*(n-1)次，该边对答案的贡献就为1*(n-1)*w[i]了。
子树大小由dfs算得即可，因为这是有根树。如果是图的话就不能这么干了，因为两个节点之间不仅仅又1条路径，这时候多源最短路只能用floyd做了。时间复杂度为O(n^3)。
本题第一次计算任意两点间距离之和：初始化子树大小DFS复杂度O(n)，算每条边的贡献O(n)，更改边长复杂度O(1)。

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
#include<iostream>
#include<list>
using namespace std;
int n,m;
long long father[100005],w[100005];
list<int> children[100005];
long long treesize[100005];
void dfs(int node){//获得子树大小
    if(children[node].size()==0){
        treesize[node]=1;
        return;
    }
    long long tot=0;
    for(list<int>::iterator i=children[node].begin();i!=children[node].end();i++){
        dfs(*i);
        tot+=treesize[*i];
    }
    treesize[node]=tot+1;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>father[i]>>w[i];
        children[father[i]].push_back(i);
    }
    dfs(1);
    long long tot=0;
    for(int i=2;i<=n;i++){
        tot+=treesize[i]*(n-treesize[i])*w[i];
    }
    cout<<tot<<endl;
    cin>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        long long change=treesize[a]*(n-treesize[a])*(b-w[a]);
        tot+=change;
        cout<<tot<<endl;
        w[a]=b;
    }
}

洛谷 【模板】树状数组 1

发表评论

题号：3374

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
struct treearray{
    const static int MAX=500005;
    int C[MAX];
    treearray(){
        memset(C,0,sizeof(C));
    }
    int lowbit(int i){
        return i&(-i);
    }
    void update(int i,int n){
        while(i<=MAX){
            C[i]+=n;
            i+=lowbit(i);
        }
    }
    int sum(int k){
        int sum=0;
        while(k>0){
            sum+=C[k];
            k-=lowbit(k);
        }
        return sum;
    }
}ta;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        ta.update(i,t);
    }
    for(int i=1;i<=m;i++){
        int p1,p2,p3;
        cin>>p1>>p2>>p3;
        switch(p1){
        case 1:
            ta.update(p2,p3);
            break;
        case 2:
            cout<<(ta.sum(p3)-ta.sum(p2-1))<<endl;
            break;
        }
    }
}

THU2017spring 2-3 Rebuild 题解

发表评论

THU2017spring 2-3 Rebuild

描述

某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的先序遍历序列和中序遍历序列，试输出其对应的后序遍历序列。

输入

第一行为一个整数n。

第二、三行，即已知的先序、中序遍历序列，数字之间以空格分隔。

输出

仅一行。

若所给的先序、中续遍历序列的确对应于某棵二叉树，则输出其后序遍历序列，数字之间以空格分隔。否则，输出-1。

输入样例1

5
1 2 4 5 3
4 2 5 1 3

输出样例1

4 5 2 3 1

输入样例2

4
2 3 1 4
4 2 1 3

输出样例2

-1

输入样例3

8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8

输出样例3

4 1 2 7 8 6 3 5

限制

1 <= n <= 500,000

输入和输出的遍历序列均为[1, n]内整数的一个排列，整数间均以空格分隔。

时间：1 sec

空间：256 MB

提示

● 注意观察特殊节点在不同遍历序列中的位置

● 提示(.docx)：

对应输入样例1的树结构:

先序遍历序列：12453
中序遍历序列：42513
注意到根节点就是先序序列的首元素，找到根节点后，根据根节点在中序序列中的位置，可划分出左右子树。

 

代码：（一个点TLE没过，其它都OK）
继续阅读 →