这题一开始没注意到d的范围，所以没做出来。

这里我们可以想到的是，我们对询问反向涂色，那么对于已经涂过的点的颜色就是最终颜色，那么就减少了很多重复的不必要操作。

然后因为d最大只有10，所以我们维护每个点已经涂到过的最远距离之后，暴搜染色的复杂度就最大为10 * m左右。（即d从0开始一直+1）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18 + 5
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

int n,m,ans[N],mx[N];
vector<int> G[N];
struct Node{
    int v,d,c;
}p[N];
vector<int> vec[N];
void dfs(int u,int fa,int d,int c) {
    if(d == -1 || mx[u] >= d) return ;
    if(ans[u] == -1) ans[u] = c;
    mx[u] = d;
    for(auto v : G[u]) {
        if(v == fa) continue;
        dfs(v,u,d - 1,c);
    }
}
int main()
{
    n = read(),m = read();
    while(m--) {
        int x,y;x = read(),y = read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int q;q = read();
    for(int i = 1;i <= q;++i) p[i].v = read(),p[i].d = read(),p[i].c = read();
    for(int i = 1;i <= n;++i) mx[i] = -1,ans[i] = -1;
    for(int i = q;i >= 1;--i) {
        if(p[i].d <= mx[p[i].v]) continue;
        dfs(p[i].v,0,p[i].d,p[i].c);
    }
    for(int i = 1;i <= n;++i) if(ans[i] == -1) ans[i] = 0;
    for(int i = 1;i <= n;++i) printf("%d\n",ans[i]);
    system("pause");
    return 0;
}

View Code