思维题

刚刚开始拿到这个题目的时候感觉应该会很麻烦，并且一开始的思路就是错的，想到了去建一个最小生成树，那么后序该怎么比较呢，就感觉很烦，后序看了大佬的题解，原来这是一个思维题，首先我们对n-1条边进行赋值操作就让它指向一个对应的值，然后在对后序n-1条边进行判断，题目根本不需要我们建图只需要我们去判断相差几条边，因为边的总数是不变的，所以就是说你每增加一条边就会相应的减少一条边，这是人为的去想的，但是代码只需要求出一共需要修改几条边，所以我们就对剩下的边进行操作，如果给出的这两个点之间没有边，那么说明就要在这个两个点之间连一条边，同时对应的减去一条边，ans是修改的次数，每修改一次就加一个这就是最终的答案

方法一：正方向求解

正反向求解是求一共需要修改多少条边，也就是一共有多少条边不同

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
    int n, u, v, ans;
    while (~scanf("%d", &n))
    {
        ans = 0;
        for (int i = 1; i <= n - 1; ++i)
        {
            scanf("%d%d", &u, &v);
            a[u] = v;//进行赋值操作
        }
        for (int i = 1; i <= n - 1; ++i)
        {
            scanf("%d%d", &u, &v);
            if (a[u] != v && a[v] != u)//如果这两个点之间没有边
                ++ans;
        }
        printf("%d\n", ans);
    }
}

方法二：反方向求解

反方向求解就是求出一共有多少条边相同，然后就用总数减去相同的数量就是需要修改的数量

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
    int n, u, v, ans;
    while (~scanf("%d", &n))
    {
        ans = 0;
        for (int i = 1; i <= n - 1; ++i)
        {
            scanf("%d%d", &u, &v);
            a[u] = v;
        }
        for (int i = 1; i <= n - 1; ++i)
        {
            scanf("%d%d", &u, &v);
            if (a[u] == v || a[v] == u)
                ++ans;
        }
        printf("%d\n", n - 1 - ans);
    }
}