Educational Codeforces Round 125

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
F(2-SAT,tarjan,scc)

题目

https://codeforces.com/contest/1657/problem/F

一个树上,每个点有小写字母

q个描述(<=4e5)

ai,bi 的简单路径得到字符串si , 注意方向可能a到b,也可能b到a

求一种满足上述所有描述的一种方案,或输出无法满足

范围

点数不超过4e5

字符串长度和不超过4e5

9s

1GB

题解

2-SAT

对于被字符串覆盖到的点, 如果正反字符相等,那么必定是这个字符

如果不等那么它也只有两种可能

于是问题变成了每个点有两种可能,并且选中其中一个时会决定它被覆盖的字符串上其它点的选择

这就是2-sat问题(每个点0/1 , 选定情况会决定其它的点情况,找一种可行方案)

2-sat问题的解法就是 建立有向图(注意这里是全部双向关系) ,求最大联通分量缩点,看是否有矛盾(一个点同时选了两个不同字符)

注意这里字符串在转化成图之前, 额外操作就是多个字符串覆盖到同一个点时, 有时能直接确定哪个字符是有效的,无效字符可以在转化前确定一部分

处理也很直白,同字符唯一确定,不同字符两个可能,多个字符串覆盖, 需要一个字符出现次数刚好是多个字符出现总次数一半

最大联通分量scc

上述处理以后就是scc的求解,这直接上tarjan

tarjan 主要就是

dfn 深度搜索访问记号

low 最小可达的前向点记号

stk 当前访问栈

res 结果数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tarjan(u){
    DFN[u] = Low[u] = ++Index//为节点u设定次序编号和Low初值
    Stack.push(u) //将节点u压入栈中
    for each(u,v) in E //枚举每一条边
        if (v not visited) //如果节点v未被访问过
            tarjan(v) //继续向下找
            Low[u]=min(Low[u],Low[v])
        else if (v in S) //如果节点v还在栈内
                Low[u]=min(Low[u], DFN[v])
    if ( DFN[u] == Low[u] ){ //如果节点u是强连通分量的根
        component = {}
        repeat{
            v = S.pop//将v退栈，为该强连通分量中一个顶点
            component.append(v)
            until( u == v)
        }
        print component
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(n);i++)
#define per(i,a,n) for (ll i=(ll)n-1;i>=a;i--)
#define pb push_back

const int N = 400000;
vector<int> p2[N+10];
int dep[N+10];
int fa[N+10];
char s[N+10];
map<char,vector<int> > p2charid[N+10];
vector<pair<int,char> > id2pchar;
vector<int> id2scc;
vector<vector<int> > scc2ids ;
vector<bool> vis ;
char ans[N+10];

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  vector<vector<int> > p;
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1);
    dfn = vector<int>(n+1);
    stk = {};
    res = vector<int> (n+1);
    p = vector<vector<int> >(n+1);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
  void p2(int i,int j){
    p[i].pb(j);
  }
};

void build(int idx,int father){
  fa[idx] = father;
  dep[idx] = dep[father]+1;
  for(auto x:p2[idx]) {
    if(x == father)continue;
    build(x, idx);
  }
}

// 因为要具体路径, LCA帮不上忙,直接暴力找
vector<int> getpath(int u,int v){
  if(dep[u] > dep[v])swap(u,v);
  vector<int> r1 = {};
  vector<int> r2 = {};
  while(dep[v] > dep[u]){
    r1.push_back(v);
    v = fa[v];
  }
  while(u != v){
    r1.push_back(v);
    v = fa[v];
    r2.push_back(u);
    u = fa[u];
  }
  r1.push_back(u);
  per(i,0,r2.size()){
    r1.push_back(r2[i]);
  }
  return r1;
}

bool add(int u,int v, Tarjan &t){
  vector<int> path = getpath(u, v);
  // 只记录不确定的
  vector<int>inc;
  vector<int>dec;
  rep(i,0,(int)path.size()){
    int p = path[i];
    char ch1 = s[i];
    char ch2 = s[path.size() - 1 -i];
    if(ch1 == ch2){ // 直接确定
      if(ans[p] != 0 && ans[p] != ch1){
        return false;
      }
      ans[p] = ch1; // 一个的改值, 两个的是 增加统计
    }else{ // 先建立关系 不关心冲突
      int id = id2pchar.size();
      id2pchar.push_back({p,ch1});
      p2charid[p][ch1].push_back(id);
      inc.pb(id);

      id = id2pchar.size();
      id2pchar.push_back({p,ch2});
      p2charid[p][ch2].push_back(id);
      dec.pb(id);
    }
  }
  assert(dec.size() == inc.size());
  rep(i,0,(int)inc.size()){
    t.p2(inc[i],inc[(i+1)%inc.size()]);
    t.p2(dec[i],dec[(i+1)%dec.size()]);
  }
  return true;
}

bool checkscc(int scc){
  vector<pair<int,char>> pch;
  for(auto id:scc2ids[scc]){
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch || ans[p] == 0){
      pch.push_back({p,ch});
    }else{
      return false;
    }
  }
  sort(pch.begin(),pch.end());
  rep(i,1,(int)pch.size()){
    if(pch[i-1].first != pch[i].first) continue; // 同一个点
    if(pch[i-1].second != pch[i].second) return false; // 不同字符
  }
  return true;
}

bool applyscc(int scc){
  vis[scc] = true;
  for(auto id:scc2ids[scc]){
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch)continue;
    if(ans[p] == 0){
      ans[p] = ch;
    }else{
      return false;
    }
  }
  return true;
}

bool rmscc(int scc){
  vis[scc] = true;
  for(auto id:scc2ids[scc]){
    if(id == 1)continue;
    auto [p, ch] = id2pchar[id];
    if(ans[p] == ch) return false; // 失效和已经填入的冲突
    if(p2charid[p].count(ch)){
      p2charid[p].erase(ch);
      if(ans[p] == 0 && p2charid[p].size() == 0)return false; //
      if(p2charid[p].size() == 1){
        auto [ch,ids] = *p2charid[p].begin();
        if(ans[p] != 0 && ans[p] != ch)return false;
        ans[p] = ch;
        for(auto id:ids){
          if(!vis[id2scc[id]]){
            int r = applyscc(id2scc[id]);
            if(!r)return r;
          }
        }
      }
    }
  }
  return true;
}

int main(){
  id2pchar.push_back({-1,'X'}); // 占位0
  id2pchar.push_back({-1,'X'}); // 建立特殊失效节点, 下标为1
  int n,q;
  cin>>n>>q;
  rep(i,0,n-1){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
    p2[v].push_back(u);
  }
  build(1,0); // 父节点和深度
  Tarjan t(2*N+2);
  rep(i,0,q){
    int u,v;
    scanf("%d %d",&u,&v);
    scanf("%s",s);
    bool r = add(u,v,t);
    if(!r){
      printf("NO\n");
      return 0;
    }
  }
  // 处理每个点明确不可能的情况
  rep(i,1,n+1) {
    if(ans[i]){ // 已确定的
      for(auto [ch,ids]:p2charid[i]){
        if(ch == ans[i])continue;
        for(auto id: ids){
          t.p2(1,id); // 失效的
          t.p2(id,1); // 失效的
        }
      }
    }else{ // 未确定的
      if(p2charid[i].size() == 0){
        ans [i] = 'a'; // 没有限制
      }else { // 每次贡献两个不同的,那么答案要占恰好一半出现
        int total = 0;
        for(auto [ch,ids]:p2charid[i]){
          total+=ids.size();
        }
        for(auto [ch,ids]:p2charid[i]){
          if((int)ids.size()*2 != total){
            for(auto id: ids){
              t.p2(1,id); // 建立不可能
              t.p2(id,1);
            }
          }
        }
      }
    }
  }
  id2scc = t.calc();
  scc2ids = vector<vector<int>>(id2pchar.size());
  vis = vector<bool>(id2pchar.size());
  rep(i,1,(int)id2pchar.size()){
    scc2ids[id2scc[i]].pb(i);
  }
  // 处理掉直接不可能
  bool r = rmscc(1);
  if(!r){
    printf("NO\n");
    return 0;
  }
  rep(scc,2,(int)id2pchar.size()){
    if(!scc2ids[scc].size())continue;
    if(vis[scc])continue;
    if(!checkscc(scc)){
      bool r = rmscc(scc);
      if(!r){
        printf("NO\n");
        return 0;
      }
    }else{
      bool r = applyscc(scc);
      if(!r){
        printf("NO\n");
        return 0;
      }
    }
  }
  rep(i,1,n+1){
    if(!ans[i]){
      printf("NO\n");
      return 0;
    }
  }
  printf("YES\n");
  rep(i,1,n+1){
    printf("%c",ans[i]);
  }
  printf("\n");
  return 0;
}

总结

还是知识点不够, 一个是太久没写tarjan scc,一个是没搞过2-sat

参考

官方题解