首页 > 代码库 > HDU 5039 Hilarity 线段树
HDU 5039 Hilarity 线段树
首先对于一棵树，如果要求点u->v路径上的边权值的1的个数为奇数的话，相当与异或和为一，而u->v的值始终与1->u xor 1->v 相等
有了这个性质之后，直接选一个点为根，dfs遍历整颗树，就可以求出根节点到其他所有节点路径上的异或和了。然后题目所要求的方案数相当与从所有为0的路径中和所有为1的路径中选一条的总种类数，还要乘2，因为还要考虑方向。
剩下的就是如何处理修改边权值的情况。首先如果修改了一个边u->v的权值之后，显然根到v的所有子节点的值都改变了，因此第一遍dfs遍历树的时候，记录一个时间戳，表示的是进入和结束遍历某一个节点的时间，那么这两个值之间的就是这个节点的所有字节点了。这样就把一个在树上的问题转化为在线性数据结构上的问题了，用线段树维护一下，就是一个简单的区间修改问题了。
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional> using namespace std; #define MP make_pair#define PB push_back#define lson rt << 1, l, mid#define rson rt << 1 | 1, mid + 1, rtypedef long long LL;typedef unsigned long long ULL; typedef vector<int> VI; typedef pair<int, int> PII;typedef pair<double, double> PDD;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 3e4 + 10;int head[maxn], nxt[maxn << 1], v[maxn << 1], w[maxn << 1], sz;int n, m, pval[maxn], lbound[maxn], rbound[maxn], ncnt;int sum[maxn << 2], lazy[maxn << 2];map<string, int> name_id;char buf1[1024], buf2[1024];bool vis[maxn];PII edge[maxn];void adde(int uu, int vv, int ww) { w[sz] = ww; v[sz] = vv; nxt[sz] = head[uu]; head[uu] = sz++;}void dfs(int now, int val) { vis[now] = true; pval[++ncnt] = val; lbound[now] = ncnt; for(int i = head[now]; ~i; i = nxt[i]) if(!vis[v[i]]) { dfs(v[i], val ^ w[i]); } rbound[now] = ncnt;}int calc(int cnt) { return cnt * (n - cnt) * 2;}void pushup(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void seg_xor(int rt, int l, int r) { lazy[rt] ^= 1; sum[rt] = r - l + 1 - sum[rt];}void pushdown(int rt, int l, int r) { if(lazy[rt]) { int mid = (l + r) >> 1; seg_xor(lson); seg_xor(rson); lazy[rt] = 0; }}void build(int rt, int l, int r) { int mid = (l + r) >> 1; lazy[rt] = 0; if(l == r) sum[rt] = pval[l]; else { build(lson); build(rson); pushup(rt); }}void update(int rt, int l, int r, int ql, int qr) { if(ql <= l && qr >= r) seg_xor(rt, l, r); else { int mid = (l + r) >> 1; pushdown(rt, l, r); if(ql <= mid) update(lson, ql, qr); if(qr > mid) update(rson, ql, qr); pushup(rt); }}int main() { int T; scanf("%d", &T); for(int kase = 1; kase <= T; kase++) { name_id.clear(); sz = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%s", buf1); name_id[string(buf1)] = i; head[i] = -1; } for(int i = 1;i < n;i++) { int u, v, w; scanf("%s%s%d", buf1, buf2, &w); u = name_id[string(buf1)]; v = name_id[string(buf2)]; adde(u, v, w); adde(v, u, w); edge[i] = MP(u, v); } memset(vis, 0, sizeof(vis)); ncnt = 0; dfs(1, 0); build(1, 1, n); scanf("%d", &m); printf("Case #%d:\n", kase); for(int i = 0; i < m; i++) { char cmd; scanf(" %c", &cmd); if(cmd == ‘Q‘) printf("%d\n", calc(sum[1])); else { int eid; scanf("%d", &eid); int u = edge[eid].first, v = edge[eid].second; if(lbound[u] < lbound[v]) swap(u, v); int ql = lbound[u], qr = rbound[u]; update(1, 1, n, ql, qr); } } } return 0;}
HDU 5039 Hilarity 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。