树

• 基环树
• DFS树

[CF1325C] Ehab and Path-etic MEXS
https://codeforces.com/contest/1325/problem/C

给一棵树的边附上0~n-2的权值,使得Mex(u,v)的最大值最小

思路:只需要考虑0,1,2的情况

对于所有不经过0的路径,mex = 0

对于所有不经过1\2,但经过0的路径,mex = 1\2

这样就可以满足所有情况

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5 + 5;
struct node{
    int to, id;
};
vector<node> e[maxn];
int x[maxn], y[maxn];
int vis[maxn];
int ans[maxn];
int l, r;
void dfs(int u,int fa) {
    int sz = e[u].size();
    for (int i = 0; i < sz;i++) {
        int v = e[u][i].to;
        int id = e[u][i].id;
        if(v==fa||vis[id])
            continue;
        ans[id] = l++;
    }
    for (int i = 0;i<sz;i++) {
        int v = e[u][i].to;
        int id = e[u][i].id;
        if(v==fa||vis[id])
            continue;
        vis[id]++;
        dfs(v, u);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1;i++) {
        scanf("%d %d", &x[i], &y[i]);
        e[x[i]].push_back((node){y[i], i});
        e[y[i]].push_back((node){x[i], i});
    }
    l = 0, r = n - 2;
    int d = 0;
    int m = 0;
    for (int i = 1; i <= n;i++) {
        int sz = e[i].size();
        if(sz>d) {
            d = sz;
            m = i;
        }
    }
 
    dfs(m, -1);
    for (int i = 0; i < n-1;i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

[CF1325F]Ehab’s Last Theorem
令t为ceil(sqrt(n))

解法一:考虑DFS树的原理,如果从$u$到$v$,经过的不是$(u,v)$这条边,说明先前存在另一条路径使得$u$到$v$,那么此时可以形成一个环,具体的见这篇文章: https://codeforces.com/blog/entry/68138

并且!如果一个点的dfs子树中所有的点都不能与它满足构成长度大于t的环这个条件,也就是情况2,那么这个点就可以存在于独立点集中

if(!vis[u]) {
       for(int v:e[u]) {
           vis[v] = 1;
       }
   }

u必然不会存在与一个长度大于t的环当中,那么它必然在独立集里,则把它的连边全部标记起来。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int t;
int dep[maxn];
int f[maxn],vis[maxn];
vector<int> e[maxn];
void dfs(int u,int fa) {
    for(int v:e[u]) {
        if(!dep[v]) {
            dep[v] = dep[u] + 1;
            f[v] = u;
            dfs(v, u);
        } 
        else {
            if(dep[v]-dep[u]+1>=t) {
                printf("2\n");
                int len = dep[v] - dep[u] + 1;
                printf("%d\n", len);
                int cnt = 0;
                while(v) {
                    if(cnt==len)
                        break;
                    cnt++;
                    printf("%d ", v);
                    v = f[v];
                }
                exit(0);
            }
        }
    }
    if(!vis[u]) {
        for(int v:e[u]) {
            vis[v] = 1;
        }
    }
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    t = ceil(sqrt(n));
    for (int i = 1; i <= m;i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dep[1] = 1;
    dfs(1, 0);
    printf("1\n");
    int cnt = 0;
    for (int i = 1; i <= n;i++) {
        if(cnt==t)
            break;
        if(!vis[i]) {
            printf("%d ", i);
            cnt++;
        }
    }
}

解法2：

一个结论：如果一张图里的每个点的度数都大于$d$,那么必然存在一个环，长度为$d+1$

在寻找环的过程中将所有度数小于$t-1$的点的邻边都删掉，这个点作为独立集的备选

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
set<pair<int,int> > s;
vector<int> v[maxn];
bool del[maxn];
int deg[maxn],occ[maxn];
void remove(int x)
{
    if (del[x])
    return;
    s.erase({deg[x],x});
    del[x]=1;
    for (int u:v[x])
    {
        if (!del[u])
        {
            s.erase({deg[u],u});
            deg[u]--;
            s.insert({deg[u],u});
        }
    }
}

int main()
{
    int n, m,sq;
    scanf("%d%d",&n,&m);
    sq = ceil(sqrt(n));
    while (m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }

    for (int i=1;i<=n;i++)
    s.insert({deg[i],i});
    vector<int> ans;
    while (!s.empty())
    {
        auto p=*s.begin();
        s.erase(s.begin());
        if (p.first+1>=sq)//度数大于等于sq-1
        {
            printf("2\n");
            vector<int> d({p.second});
            occ[p.second]=1;
            while (1)
            {
                pair<int,int> nex(1e9,0);
                for (int u:v[d.back()])
                {
                    if (!del[u])
                    nex=min(nex,make_pair(occ[u],u));
                }
                if (nex.first)
                {
                    printf("%d\n",(int)d.size()-nex.first+1);
                    for (int i=nex.first-1;i<d.size();i++)
                    printf("%d ",d[i]);
                    return 0;
                }
                d.push_back(nex.second);
                occ[nex.second]=d.size();
            }
        }
        //度数小于sq-1
        ans.push_back(p.second);
        remove(p.second);//删除所有邻边
        for (int u:v[p.second])//双向删除
        remove(u);
    }
    printf("1\n");
    for (int i=0;i<sq;i++)
    printf("%d ",ans[i]);
}

[CF1139C] Edgy Tree
https://codeforces.com/contest/1139/problem/C

题意:一棵树,且需要构建长度为k的序列,序列中相邻两点的路径一定经过”黑边”,节点可以重复

思路:”黑边”不加入连通块,将”红边”的各个连通块的大小找出来,减去这一部分构造的长度为k的序列

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> e[maxn];
int vis[maxn];
const long long mod = 1e9 + 7;
#define add(x, y) (x + y) % mod;
int dfs(int u,int fa) {
    int sz = e[u].size();
    long long ret = 1;
    vis[u]++;
    for (int i = 0; i < sz;i++) {
        int v = e[u][i];
        if(v==fa||vis[v]){
            continue;
        }
        ret += dfs(v, u);
    }
    return ret;
}
long long qpow(long long x,int k) {
    long long ret = 1;
    while(k) {
        if(k&1)
            ret = ret * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ret;
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n - 1;i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if(!w) {
            e[x].push_back(y);
            e[y].push_back(x);
        }
    }
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            continue;
        long long cnt = dfs(i, -1);
        long long x = qpow(cnt, k);
        sum = add(sum, x);
    }
    long long ans = qpow(n, k);
    ans = (ans - sum + mod) % mod;
    cout << ans << endl;
}