树

题目链接:后序遍历

struct node
{
    int l,r;
    char val;
    node():l(0),r(0),val(0) {}
} tree[100];

char qian[100],zhong[100];
int cont=1,n;

void buildtree(int id,int ql,int qr,int zl,int zr)
{
    tree[id].val=qian[ql];
    if(ql==qr)return;
    int i;
    for(i=zl; i<=zr; i++)
        if(qian[ql]==zhong[i])break;
    if(zl<=i-1)buildtree(tree[id].l=++cont,ql+1,ql+i-zl,zl,i-1);
    if(i+1<=zr)buildtree(tree[id].r=++cont,ql+i-zl+1,qr,i+1,zr);
}

void dfs(int x)
{
    if(tree[x].l)dfs(tree[x].l);
    if(tree[x].r)dfs(tree[x].r);
    if(tree[x].val)
    {
        printf("%c",tree[x].val);
        if(++cont==n)printf("\n");
    }
}

int main()
{
    scanf("%s%s",qian+1,zhong+1);
    n=strlen(qian+1);
    buildtree(1,1,n,1,n);
    cont=0;
    dfs(1);
    return 0;
}

题目链接:树的直径

bfs:

struct node
{
    int id,s;
    node(int id,int s):id(id),s(s){}
};

bool vis[100005];
vector<int>G[100005];

pair<int,int>bfs(int st)
{
    queue<node>Q;
    memset(vis,false,sizeof(vis));
    Q.push(node(st,0));
    vis[st]=true;
    int maxx_point=st,maxx_step=0;
    while(!Q.empty())
    {
        node temp=Q.front();
        maxx_point=temp.id,maxx_step=temp.s;
        Q.pop();
        int len=G[temp.id].size();
        for(int i=0;i<len;i++)
        {
            int nex=G[temp.id][i];
            if(!vis[nex])
            {
                vis[nex]=true;
                Q.push(node(nex,temp.s+1));
            }
        }
    }
    return make_pair(maxx_point,maxx_step);
}

int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int ans=bfs(bfs(1).first).second;
    printf("%d\n",ans);
    return 0;
}

dfs:

vector<int>G[100005];
bool vis[100005];
int maxx=0;

int dfs(int x)
{
    vis[x]=true;
    int len=G[x].size();
    if(len==0)return 0;
    int fir=0,sec=0;
    for(int i=0; i<len; i++)
        if(!vis[G[x][i]])
        {
            int t=dfs(G[x][i]);
            if(t>fir)sec=fir,fir=t;
            else if(t>sec)sec=t;
        }
    if(fir+sec>maxx)maxx=fir+sec;
    return fir+1;
}

int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=0; i<n-1; i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    printf("%d\n",maxx);
    return 0;
}