Codeforces Round #835 (Div. 4) A-G Complete Problem Solving-G、
最编程
2024-03-10 13:59:11
...
首先，如果不能跳跃，那么肯定就是 \(S\) 到 \(T\) 的链的异或值。
考虑跳跃。那么我们的路径就成为了以 \(S\) 且不越过 \(T\) 的一条链加上以 \(T\) 为起点的另外一条链。
为什么是链？因为走回头路相当于这一段是无效操作。
为什么 \(S\) 开始不能越过 \(T\)? 因为直接走路的话不能进 \(T\)。
为什么 \(T\) 可以越过 \(S\)? 因为可以先去 \(S\) 的另外一棵子树，再去这一课子树。
上述操作也包含了不传送的情况。（原地TP）。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
struct node{
int u, v, next;
ll w;
} t[N << 1];
int head[N];
int bian = 0;
inline void addedge(int u, int v, ll w){
t[++bian] = (node){u, v, head[u], w}, head[u] = bian;
return ;
}
int n, S, T;
map <ll, bool> g;
ll dis1[N];
ll dis2[N];
bool vis1[N], vis2[N];
void dfs1(int u){
if(u == T) return ;
vis1[u] = 1;
for(int i = head[u]; i; i = t[i].next){
int v = t[i].v;
if(!vis1[v]){
dis1[v] = dis1[u] ^ t[i].w;
dfs1(v);
}
}
return ;
}
void dfs2(int u){
// if(u == S) return ;
vis2[u] = 1;
for(int i = head[u]; i; i = t[i].next){
int v = t[i].v;
if(!vis2[v]){
dis2[v] = dis2[u] ^ t[i].w;
dfs2(v);
}
}
return ;
}
void clear(int n){
g.clear();
for(int i = 1; i <= n; i++)
dis1[i] = dis2[i] = 0;
for(int i = 1; i <= n; i++)
head[i] = 0, vis1[i] = vis2[i] = 0;
bian = 0;
return ;
}
int main(){
int testcase; cin >> testcase;
while(testcase--){
clear(n);
cin >> n >> S >> T;
for(int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
dfs1(S);
dfs2(T);
for(int i = 1; i <= n; i++)
if(vis1[i]) g[dis1[i]] = 1;
bool flag = 0;
for(int i = 1; i <= n; i++){
if(vis2[i] && i != T)
if(g[dis2[i]] == 1){
flag = 1;
break;
}
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
原文地址：https://www.cnblogs.com/wondering-world/p/16919330.html