[abc] D. Coloring Edges on Tree 边染色 DFS

前言

我去,看错了,给我整坏了QAQ 传送门 :

思路

题意: 给你一个图,让你给他们染色,使得一个节点不会连两条相同颜色的边,问最小的颜色数量是多少

既然是要使颜色数量最小,我们都能直接想到是从节点边数最多的边开始,然后看了一眼样例,发现答案正好是度数最大节点的度数

处理输出的时候,我们需要使用map和pii存一下边的信息,(写着写着写成点了QAQ) 然后直接输出即可

CODE

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define x first
#define y second

const int N  = 1e5+10;
vector g[N];
int in[N],color[N],ans[N];
typedef pair pii;
map mp;
pii deg[N];

void dfs(int u,int fa,int color,int maxn)
{
    ans[u] = color;
    for(auto x : g[u])
    {
        if(x!=fa)
        {

            mp[{u,x}] = mp[{x,u}] = color;
            color = (++color)%(maxn);
          ///  ans[x] = color == 0 ? ++color:color;
            dfs(x,u,color,maxn);
        }
    }
}
void solve()
{
    int n;cin>>n;
    int maxn = 0 ,pos = 0 ;
    for(int i=1;i>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        in[a]++;
        in[b]++;
        deg[i].x = a;
        deg[i].y = b;

        if(maxn