正解不道为什么又是并查集。

树性质部分分

考虑树部分分，发现所有颜色为 c 的城市必须构成一个连通的子树，且路径上不能出现其他颜色。

对每种颜色 c，定义 $S_c$ 为树中连接所有颜色 c 城市的最小连通子树点集合。

如果 $S_c$ 中出现了另一种颜色 d 的城市，那么：

政党 c 访问时一定会经过这个 d 城市；

为了让这个城市最终投给 d，政党 d 必须在 c 之后访问。

所以得到一条有向边：

$c \to d$ 含义是：正序中 c 必须早于 d。

于是问题变成：

在颜色集合上建出这个有向图，判断它是否无环。 若无环，按拓扑序安排政党即可；若有环，则不可能。

在 oirush 能拿到 52 分，luogu 只有 10 分（一个 subtask）。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int LOG = 17;

int n, k, m;
int a[N];
vector<int> G[N];      // 树
vector<int> color[N];    // color[c] = 颜色 c 的所有城市

int up[N][20], dep[N], dfn[N], rid[N], tsp;

void dfs(int u, int fa) {
    dfn[u] = ++tsp;
    dep[u] = dep[fa] + 1;
    up[u][0] = fa;
    for (int j = 1; j < LOG; j++)
        up[u][j] = up[up[u][j - 1]][j - 1];
    for (int v : G[u])
        if (v != fa) dfs(v, u);
    rid[u] = tsp;
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	for (int i = LOG - 1; i >= 0; i --) {
		if (dep[up[x][i]] >= dep[y]) {
			x = up[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = LOG - 1; i >= 0; i --) {
		if (up[x][i] != up[y][i]) {
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while (T--) {
        cin >> n >> m >> k;

        // 清空
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int c = 1; c <= k; c++) color[c].clear();

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            color[a[i]].push_back(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int u, v; cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        // 预处理 LCA
        tsp = 0;
        dep[0] = 0;
        dfs(1, 0);

        // 建依赖图：c -> d 表示正序中 c 必须早于 d
        vector<vector<int>> tp(k + 1);
        set<pair<int,int>> seen;   // 去重用的 

        for (int c = 1; c <= k; c++) {
            if (color[c].empty()) continue;

            // 求 S_c 全体点的 LCA
            // 只需取 dfn 最小和最大的点，它们的 LCA 就是整组的 LCA
            int mn = color[c][0], mx = color[c][0];
            for (int u : color[c]) {
                if (dfn[u] < dfn[mn]) mn = u;
                if (dfn[u] > dfn[mx]) mx = u;
            }
            int L = LCA(mn, mx);

            // T_c = 所有颜色 c 的点到 L 的路径的并集
            // 沿途遇到颜色 d != c 的点，就加边 c -> d
            for (int u : color[c]) {
                for (int x = u; x != L; x = up[x][0]) {
                    int d = a[x];
                    if (d != c && seen.insert({c, d}).second)
                        tp[c].push_back(d);
                }
            }
            if (a[L] != c && seen.insert({c, a[L]}).second)
                tp[c].push_back(a[L]);
        }

        // 拓扑排序判环
        vector<int> indeg(k + 1, 0);
        for (int c = 1; c <= k; c++)
            for (int d : tp[c])
                indeg[d]++;

        queue<int> q;
        for (int c = 1; c <= k; c++)
            if (indeg[c] == 0) q.push(c);

        int cnt = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            cnt++;
            for (int v : tp[u])
                if (--indeg[v] == 0) q.push(v);
        }

        cout << (cnt >= k ? "TAK" : "NIE") << '\n';
    }
    return 0;
}

正解

树中路径唯一，所以依赖关系非常清晰， $S_c$ 内部的“缺口”就是路径上的其他颜色。

一般图中，$S_c$ 中的点可能通过多条路径连接，而且路径上可能经过其他颜色的点。但这些其他颜色的点如果最终不是 c，说明它们被更晚的政党覆盖了。因此，这些点可以作为“桥梁”帮助 c 连通，只要它们比 c 更晚被访问。

这也许预示着要倒序处理？

考虑最后一步的政党 c，其 $S_c$ 必须在原图中是连通的。

确定 c 后，$S_c$ 中的所有点都被染成 c，并且它们之后不会被覆盖。对于更早的政党来说，这些点可以被随意经过，因为经过后会被 c 重新覆盖，不影响最终颜色。

所以，这些已经确定的点可以视为“灰色”的通道。

于是我们维护一个集合 $S_{\text{end}}$（灰点），初始时加入所有 $S_c$ 本身连通的颜色 c。然后不断扩展：

从队列中取出一个颜色，把它的所有点加入 $S_{\text{end}}$ 。

对于还未确定的颜色 c′ ，如果 $S_{c'}$ 能够借助 $S_{\text{end}}$ 中的某些点连接成一个连通块（即存在 $T \subseteq S_{\text{end}}$，使得 $S_{c'} \cup T$ 连通），那么 c′ 就可以作为下一个“最后一步”，加入队列。

考虑使用并查集来维护灰点与非灰点之间的联通。

最后有所有颜色都被确定，或者无法继续。全部确定则合法，否则不合法。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, k, m;
int a[N];
vector<int> G[N]; 
vector<int> color[N];    // color[c] = 颜色 c 的所有城市
int cnt[N];              // cnt[c]：颜色 c 内部已发生的有效合并次数
queue<int> Q;
bool vis[N];       // vis[c] = true 表示颜色 c 已被确定（其点已变灰）

void fun(int x);         // 前向声明

// dsu2：非灰点之间的并查集，只合并同色点
struct dsu2 {
    int fa[N];
    void init() {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int findfa(int x) {
        if (x == fa[x]) return x;
        return fa[x] = findfa(fa[x]);
    }
    void merge(int x, int y) {
        x = findfa(x);
        y = findfa(y);
        if (x == y) return;
        int c = a[x];          // 只合并同色点，所以根的颜色就是该颜色
        cnt[c]++;
        fa[y] = x;
        // 如果颜色 c 的所有点已经连通
        if (cnt[c] == (int)(color[c].size() - 1)) {
            Q.push(c);
            vis[c] = 1;
            fun(c);
        }
    }
} d2;

// 灰点之间的并查集
// 每个灰点连通块维护哈希表 mp[x]：mp[x][c] = 邻域中颜色 c 的一个非灰代表点
struct dsu {
    int fa[N], sz[N];
    unordered_map<int, int> mp[N];
    void init() {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            sz[i] = 1;
            mp[i].clear();
        }
    }
    int findfa(int x) {
        if (x == fa[x]) return x;
        return findfa(fa[x]);
    }
    // 计算灰点 x 的邻域：把 x 的每个非灰邻居按颜色记入 mp[x]
    void calc(int x) {
        for (int u : G[x]) {
            int c = a[u];
            if (vis[c]) continue;       // 跳过灰点邻居
            int v = mp[x][c];
            if (!v) {                   // 该颜色还没有代表元
                mp[x][c] = u;
                continue;
            }
            // 两个同色非灰点都能通过灰点 x 连通，合并它们
            d2.merge(u, v);
        }
    }
    // 合并两个灰点连通块
    void merge(int x, int y) {
        x = findfa(x);
        y = findfa(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x;
        sz[x] += sz[y];
        // 把小连通块 mp[y] 合并进大连通块 mp[x]
        for (auto it : mp[y]) {
            int c = it.first, u = it.second;
            if (vis[c]) continue;
            int v = mp[x][c];
            if (!v) {
                mp[x][c] = u;
                continue;
            }
            // 两个灰点连通块都能“看到”颜色 c 的非灰点 u 和 v
            // 说明 u 和 v 可以通过灰点连通
            d2.merge(u, v);
        }
        mp[y].clear();
    }
} d;

// 颜色 x 被确定后，遍历它的所有点，把每个点作为灰点计算邻域
void fun(int x) {
    for (int u : color[x]) {
        d.calc(u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;

        for (int i = 1; i <= n; i++) G[i].clear();
        for (int c = 1; c <= k; c++) color[c].clear();

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            color[a[i]].push_back(i);
        }
        // 注意：这里应该读入 m 条边，而不是 n-1 条
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        memset(cnt, 0, sizeof(cnt));
        memset(vis, 0, sizeof(vis));
        d2.init();
        d.init();

        // 初始时，大小为 1 的颜色天然连通，可以直接确定
        for (int i = 1; i <= k; i++) {
            if (color[i].size() == 1) {
                Q.push(i);
                vis[i] = 1;
                fun(i);
            }
        }

        // 初始时，把原图中同色且相邻的点合并
        for (int i = 1; i <= n; i++) {
            for (int j : G[i]) {
                if (i < j && a[i] == a[j]) {
                    d2.merge(i, j);
                }
            }
        }

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            // 颜色 u 的点已经全部变灰，把每个灰点与它的灰点邻居合并
            for (int x : color[u]) {
                for (int y : G[x]) {
                    if (vis[a[y]]) {     
                        d.merge(x, y);
                    }
                }
            }
        }

        // 检查是否所有实际出现的颜色都被确定
        int totco = 0, dm = 0;
        for (int c = 1; c <= k; c++) {
            if (!color[c].empty()) {
                totco++;
                if (vis[c]) dm ++;
            }
        }

        cout << (dm == totco ? "TAK" : "NIE") << '\n';
    }
    return 0;
}

题意相当于给定一个无向图，并且有 $k$ 种颜色，定义一个合法的染色流程为：按照某种顺序依次枚举这些颜色，考虑到某种颜色时，需要将图上一个连通块内的结点全部染成该颜色。已知一个初始时所有顶点都没有颜色的无向图，在一些操作后每个点的颜色；问当前这种状态是否可以由上面的合法染色流程得到？

直接按照这个定义去检查染色是否合法是一件很困难的事，因为你并不知道所有颜色的染色顺序。但是可以观察到一个事实：染色流程中，最后一步选定的颜色对应的结点在图上一定是一个连通块。

以下的分析中认为 $n,m,k$ 同阶。称一个点集 $S$ 连通，当且仅当这个点集的导出子图连通。设初始时颜色为 $c$ 的点集为 $S_c$。考虑倒着确定所有颜色的顺序，具体地，用一个队列维护“哪些颜色可以作为目前考虑到的最后一步”，此外再维护一个点集 $S_{\mathrm{end}}$，初始时为空。初始时放入所有满足 $S_c$ 连通的颜色 $c$，接着开始一个类似 BFS 的流程：每次取出队头的颜色，将 $S_c$ 内的所有结点加入 $S_{\mathrm{end}}$；接着暴力扫描每个还未加入过队列的颜色 $c'$，若存在一个 $S_{\mathrm{end}}$ 的子集 $T$ 满足点集 $S_{c'}\cup T$ 是连通的（说人话就是，$S_{\mathrm{end}}$ 内的结点在之后可以随便被染上其他的颜色了；此时只需要判断能不能借助这个集合中的某些结点，把颜色为 $c'$ 的结点“连起来”），那么 $c'$ 就可以作为新的“最后一步”，将其加入队列即可。借助一个并查集，可以实现一个时间复杂度为 $O(n^2)$ 的做法，很显然这并不足够。

尝试对这个做法进行优化：做法的瓶颈主要在每一轮枚举颜色暴力扫描的过程；这个过程有两个问题：（1）每次都要把 $S_{\mathrm{end}}$ 中的点考虑一遍，枚举量巨大；（2）每一轮中都要重新检查一个颜色是否满足条件，需要借助一种较为简便的方式进行代替。

对于第一个问题，称 $S_{\mathrm{end}}$ 中的点为灰点，那么若一条边在某个时刻连上了两个灰点，那么这两个灰点可以“合并”成一个点——具体地，相当于把一个灰点 $u$ 的邻域（去掉边 $(u,v)$）合并到另一个灰点 $v$ 上（即 $N_v\gets N_v\cup N_u$）：这可以使用启发式合并维护。

对于第二个问题，考虑并查集的本质，发现对于一个初始时所有点互不连通的点集 $S_c$，若在其内部发生了 $|S_c|-1$ 次“有效合并”（即调用并查集的 merge 函数时，传入的是两个不在同一个连通块里的结点），那么它就会变成一个连通块。于是可以维护每个颜色的点内部发生了多少次有效合并：当某个点 $u$ 成为灰点时，把 $u$ 的邻域中同色的点先进行并查集合并（若为有效合并，那么检查对应颜色是否可以被放入队列），再对于每个颜色只保留一个代表元，其他的边忽略掉（这是为了保证接下来启发式合并的时间复杂度）；当 $u$ 的邻域并入另一个灰点 $v$ 的邻域时，扫描 $u$ 邻域每一个结点，再查询 $v$ 邻域中有无相同颜色的结点（使用哈希表维护）：若有，那么在并查集上合并两个点（若为有效合并，检查颜色是否可以放入队列），不用将其再加入 $v$ 邻域；若没有，那么直接把它加入 $v$ 的邻域。时间复杂度是启发式合并的 $O(n\log n)$，足以通过。

::::error[一种常见的错误解法]{open} 很多现场选手在本题犯了一个从样例中无法查出的错误，即在考虑一个灰点时，把邻域中不管什么颜色的点全部在并查集中合并了。这样子代码似乎会好写很多，但是很可惜，这样的做法是错误的。以下是一个比较简单的反例（由

7 6 7
5 3 4 2 2 1 3
1 2
2 3
3 4
2 5
4 6
6 7

以下是图示：

正确答案是 NIE，但是错解会输出 TAK。如图，若采用错误的合并方式，会将结点 $2$ 与 $7$ 合并，而它们中间还隔着一个不是灰点的 $4$。 ::::

代码中哈希表选用 pbds 库的 gp_hash_table。放代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
namespace IAOI_lib{
  class dsu{
    private:
      vector<int> a,s;
    public:
      dsu(int n):a(n),s(n,1){
        iota(a.begin(),a.end(),0);
      }
      int leader(int x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      int size(int x){
        return s[leader(x)];
      }
      void merge(int x,int y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      bool same(int x,int y){
        return leader(x)==leader(y);
      }
      vector<vector<int> > groups(){
        vector<int> id(a.size(),-1);
        int c=0;
        for(int i=0;i<a.size();i++)
          if(i==leader(i))id[i]=c++;
        vector<vector<int> > v(c);
        for(int i=0;i<a.size();i++)
          v[id[leader(i)]].emplace_back(i);
        return v;
      }
  };
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m,k; cin>>n>>m>>k;
    vector<int> a(n);
    for(auto &i:a)cin>>i,i--;
    vector<vector<int> > vt(k);
    for(int i=0;i<n;i++)
      vt[a[i]].emplace_back(i);
    vector<vector<int> > g(n);
    for(int i=0;i<m;i++){
      int u,v; cin>>u>>v;
      g[--u].emplace_back(--v);
      g[v].emplace_back(u);
    }
    vector<int> e(k);
    queue<int> q;
    for(int i=0;i<k;i++)
      if(e[i]+1>=vt[i].size())
        q.emplace(i);
    IAOI_lib::dsu d(n);
    auto mg=[&](int x,int y){
      if(d.same(x,y))return;
      d.merge(x,y);
      if(++e[a[x]]+1>=vt[a[x]].size())
        q.emplace(a[x]);
    }; // 进行一次并查集合并：若为有效合并，检查是否可以将颜色放入队列
    vector<int> f(n);
    iota(f.begin(),f.end(),0);
    vector<gp_hash_table<int,int> > s(n);
    auto leader=[&](auto &&self,int x)->int{
      return x==f[x]?x:f[x]=self(self,f[x]);
    }; // 额外维护一个灰点的并查集，方便启发式合并
    auto mg2=[&](int x,int y){
      x=leader(leader,x),y=leader(leader,y);
      if(x==y)return;
      if(s[x].size()>s[y].size())swap(x,y);
      for(auto [c,l]:s[x]){
        if(s[y].find(c)!=s[y].end())mg(l,s[y][c]);
        else s[y][c]=l;
      }
      f[x]=y,gp_hash_table<int,int>().swap(s[x]);
    }; // 邻域的启发式合并
    for(int u=0;u<n;u++)
      for(int v:g[u])
        if(u<v&&a[u]==a[v])mg(u,v);
    int dl=0;
    while(!q.empty()){
      int c=q.front(); dl++,q.pop();
      for(int u:vt[c]){
        a[u]=-1;
        sort(g[u].begin(),g[u].end(),[&](int x,int y){
          return a[x]<a[y];
        });
        for(int i=0;i<g[u].size();i++)
          if(~a[g[u][i]]){
            if(i&&a[g[u][i-1]]==a[g[u][i]])
              mg(g[u][i-1],g[u][i]);
            else s[u][a[g[u][i]]]=g[u][i];
          }
      } // 合并单个邻域中颜色相同的结点，并选出代表元
      for(int u:vt[c])
        for(int v:g[u])
          if(a[v]<0)mg2(u,v);
    }
    cout<<(dl==k?"TAK\n":"NIE\n");
  }
  return 0;
}