2024-07-24 10:09:06
发布于：浙江
36阅读
0回复
0点赞
不会，求解
全部评论 4
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <set> #include <algorithm> #define MAXN 30050 using namespace std; /* 输入格式： 第一行两个正整数n和q，表示点的个数，查询和询问的总次数。 接下来n-1行，每行两个正整数u、v、w，表示u和v两个点之间有一条边权为w的边。 接下来q行，格式为1 u v或2 u v w。如果为1 u v操作， 你需要输出u到v的路径上所有子路径经过的边的边权的xor值的和是多少； 如果为2 u v w操作，你需要把u到v这条边的边权改为w，保证这条边存在。 输出格式： 对于每个1操作，输出答案。*/ int n, q, son[MAXN], size[MAXN], dep[MAXN], fa[MAXN], top[MAXN], id[MAXN], b[MAXN], num[MAXN], ecnt, tcnt, ed[MAXN]; struct node{ int v, w; node *next; node(){} node(int _v, int _w, node *_n) { v = _v, w = _w, next = _n; } }pool[MAXN<<2], *h[MAXN]; struct node2{ int num0, num1, rev; node2 operator + (const node2 &x){ node2 t; t.num0 = num0 + x.num0; t.num1 = num1 + x.num1; t.rev = 0; return t; } }t[25][MAXN<<3]; inline void addedge(int u, int v, int w){ node *p1 = &pool[ecnt++], *p2 = &pool[ecnt++]; *p1 = node(v, w, h[u]), h[u] = p1; *p2 = node(u, w, h[v]), h[v] = p2; } void dfs1(int u){ size[u] = 1; for(node *p = h[u]; p; p = p->next){ if(p->v != fa[u]){ //cout<<u<<' '<<p->v<<' '<<b[u]<<' '<<p->w<<' '<<b[p->v]<<' '; b[p->v] = b[u]^p->w; ed[p->v] = p->w; //cout<<b[p->v]<<endl; fa[p->v] = u; dep[p->v] = dep[u]+1; dfs1(p->v); size[u] += size[p->v]; if(size[p->v] > size[son[u]]) son[u] = p->v; } } } void dfs2(int u, int t){ id[u] = ++tcnt; num[tcnt] = b[u]; top[u] = t; if(!son[u]) return; dfs2(son[u], t); for(node *p = h[u]; p; p = p->next){ if(!id[p->v]) dfs2(p->v, p->v); } } void build(int k, int u, int l, int r){ if(l == r){ if((num[l]>>k)&1) t[k][u].num1 = 1; else t[k][u].num0 = 1; return; } int mid = (l+r)>>1; build(k, u<<1, l, mid); build(k, u<<1|1, mid+1, r); t[k][u] = t[k]2024-07-24 来自 浙江
0
有帮助，赞一个