提高级-算法总结--树上DFS进阶1

· · 算法·理论

OK啊，我们也是从上次的 DFS 跑到了树上。
今天直接树上 DFS！

[ABC333D] Erase Leaves

OK啊，这道题一眼就看出了暴力的解法我们的第一反应就是把 1 当根节点，然后求子树大小，可这样远不是最优答案，暴力又会 TLE，怎木班呢？
我们可以在求子树大小的时候，选取 1 节点的最大子树，然后我们可以把 1 当作这棵子树的叶子节点，就可以等他剩下的所有子树删完之后，得到答案，因为我们选的 1 的子树是最大的，所以剩下的答案一定是最小的，所以代码就出来啦！
为什么不选其他的子树都当 1 的父节点呢？
一个点有多个父节点，现实吗？ 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int siz[300005];
int n,maxn=-1;
vector<int> op[300005];
void dfs(int x,int da)
{
    siz[x]=1;
    for(int i=0;i<op[x].size();i++)
    {
        int v=op[x][i];
        if(v!=da)
        {
            dfs(v,x);
            siz[x]+=siz[v];
            if(x==1)
            {
                maxn=max(maxn,siz[v]);
            }
        }
    }
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        op[x].push_back(y);
        op[y].push_back(x);
    }
    dfs(1,0);
    cout<<n-maxn;
    return 0;
}

P7370 [COCI2018-2019#4] Wand

OK啊，这道题是一道表里不一的题。
看着像并查集，然后 WA 告诉你这道题是图论。
其实这道题我们可以注意到，有些对决在某些时候是没用的，因为魔杖不在输者手里，所以没有意义。
如果我们需要让某人拿到，就可以提前把某些对决变为没有意义的对决，所以我们最后把这个建成个图。
代码： 

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool vis[100005];
int n,m;
vector<int> op[100005];
void dfs(int x)
{
    for(int i=0;i<op[x].size();i++)
    {
        int v=op[x][i];
        if(vis[v]==false)
        {
            vis[v]=true;
            dfs(v);
        }
    }
    return;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        op[y].push_back(x);
    }
    dfs(1);
    if(op[1].size()==0)
    {
        cout<<1;
        for(int i=2;i<=n;i++) cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++) cout<<vis[i];
    return 0;
}

P9872 [EC Final 2021] DFS Order

这道题其实很水的。
我们的最短时间其实就是深度，最长的时间就是把小于等于他的深度的点全部走完的时间 ,也可以理解为：
n-siz[u]
EASY 啊！ 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dep[100005];
int siz[100005];
vector<int> op[100005];
void dfs(int x,int da)
{
    siz[x]=1;
    dep[x]=dep[da]+1;
    for(int i=0;i<op[x].size();i++)
    {
        int v=op[x][i];
        if(v!=da)
        {
            dfs(v,x);
            siz[x]+=siz[v];
        }
    }
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) op[i].clear();
        for(int i=1;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            op[x].push_back(y);
            op[y].push_back(x);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)
        {
            cout<<dep[i]<<" "<<n-siz[i]+1<<endl;
        }
    }
    return 0;
}

P8604 [蓝桥杯 2013 国 C] 危险系数

这道题其实就是一个美丽的暴力，枚举每个关键点，然后跑一遍搜索，判断1去点这个点后两点是否连通就行了！ 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
vector<int> op[1005];
int u,v;
int q[1000005];
bool vis[1005];
int head=0,tail=1;
bool work(int x)
{
    if(vis[x]==false)
    {
        head++;
        q[head]=x;
        vis[x]=true;
        if(x==v) return true;
    }
    return false;
}
bool bfs()
{
    head++;
    q[head]=u;
    vis[u]=true;
    while(head-tail+1>0)
    {
        int x=q[tail];
        tail++;
        for(int i=0;i<op[x].size();i++)
        {
            int v=op[x][i];
            if(work(v)) return true;
        }
    }
    return false;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        op[x].push_back(y);
        op[y].push_back(x);
    }
    cin>>u>>v;
    if(!bfs())
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(i==u||i==v) continue;
        for(int j=1;j<=m;j++) vis[j]=false;
        vis[i]=true;
        head=0,tail=1;
        if(!bfs()) ans++;
    }
    cout<<ans;
    return 0;
}

P9304 「DTOI-5」3-1

这道题我们分情况：
如果没有传送门，答案就是：
2*(k-1)
就相当于走一步，走回来，走一步，走回来......

可有了传送门，所以我们就可以在走了最远的时候传送回去，节省时间，这样是最大的，然后再走一步，走回来......
可要注意，我们不能走出界哦！ 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,maxn;
vector<int> op[100005];
int dep[100005];
void dfs(int x,int da)
{
    dep[x]=dep[da]+1;
    for(int i=0;i<op[x].size();i++)
    {
        int v=op[x][i];
        if(v!=da)
        {
            dfs(v,x);
        }
    } 
    maxn=max(maxn,dep[x]);
    return; 
}
signed main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        op[x].push_back(y);
        op[y].push_back(x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<2*(i-1)-min(i-1,maxn-1)<<endl;
    }
    return 0;
}

OK啊，结束了好吧，不爬树了！
下课！
ヾ(￣▽￣)Bye~Bye~