本题虽然可以用$LCA$做，但是为了练习图论，我选择使用链式前向星遍历的方法
先准备几个东西
1 a ^ 0 = a2 a ^ a = 0
然后要注意，如果每个请求都把图遍历一次的话只有$40pts$，所以我使用$xors$数组来储存
可以证明，无论取哪一个节点为出发点，$xors[u]$与$xors[v]$的异或值都是不变的
代码：
1 #include2 using namespace std; 3 4 int n, m, cnt = 0, ans, book[100005]; 5 int head[200005], xors[100005]; 6 7 struct Edge { 8 int to; 9 int val;10 int nxt;11 };12 13 Edge edge[200005];14 15 void add(int from, int to, int value) {16 ++cnt;17 edge[cnt].to = to;18 edge[cnt].nxt = head[from];19 edge[cnt].val = value;20 head[from] = cnt;21 }22 23 void get(int now, int last) {24 for(int i = head[now]; i != -1; i = edge[i].nxt) {25 if(edge[i].to != last) {26 xors[edge[i].to] = xors[now] ^ edge[i].val;27 get(edge[i].to, now);28 }29 }30 return ;31 }32 33 void solve() {34 int u, v, w;35 memset(head, -1, sizeof(head));36 scanf("%d", &n);37 for(int i = 1; i < n; i++) {38 scanf("%d%d%d", &u, &v, &w);39 add(u, v, w);40 add(v, u, w);41 }42 get(1, 0);43 scanf("%d", &m);44 for(int i = 1; i <= m; i++) {45 scanf("%d%d", &u, &v);46 printf("%d\n", xors[u]^xors[v]);47 }48 }49 50 int main() {51 solve();52 return 0;53 }
SPFA
板子，不多讲
注意：
$1.head$数组要开得和存边数组一样大
$2.$对边进行松弛之后将没有入队的元素入队的$if$条件语句要写在边的松弛的$if$语句里面！
代码：
1 #include2 using namespace std; 3 4 int n, m, s, cnt; 5 int dis[10005], head[500005], book[10005]; 6 7 struct Edge { 8 int to; 9 int nxt;10 int dis;11 };12 13 Edge edge[500005];14 15 void add(int from, int to, int dis) {16 ++cnt;17 edge[cnt].to = to;18 edge[cnt].nxt = head[from];19 edge[cnt].dis = dis;20 head[from] = cnt;21 }22 23 void spfa() {24 queue que;25 for(int i = 1; i <= n; i++) {26 dis[i] = 2147483647;27 book[i] = 0;28 }29 que.push(s);30 dis[s] = 0, book[s] = 1;31 while(!que.empty()) {32 int u = que.front();33 que.pop(), book[u] = 0;34 for(int i = head[u]; i; i = edge[i].nxt) {35 int v = edge[i].to;36 if(dis[v] > dis[u] + edge[i].dis) {37 dis[v] = dis[u] + edge[i].dis;38 if(book[v] == 0) {39 book[v] = 1;40 que.push(v);41 }42 }43 }44 }45 }46 47 void init() {48 int u, v, w;49 scanf("%d%d%d", &n, &m, &s);50 for(int i = 1; i <= m; i++) {51 scanf("%d%d%d", &u, &v, &w);52 add(u, v, w);53 }54 }55 56 void solve() {57 spfa();58 for(int i = 1; i <= n; i++) {59 printf("%d ", dis[i]);60 }61 }62 63 int main() {64 init();65 solve();66 return 0;67 }