HDU 5029 Relief grain(离线+线段树+启发式合并)(2014 ACM/ICPC Asia Regional Guangzhou Online)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5029
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII; const int MAXV = ;
const int MAXE = MAXV << ;
const int MAXT = MAXV << ; int head[MAXV], ecnt;
int to[MAXE], next[MAXE];
int n, m, maxz; void init() {
memset(head + , -, n * sizeof(int));
ecnt = ;
} void add_edge(int u, int v) {
to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++;
} #define mid ((l + r) >> 1)
struct Node {
Node *lson, *rson;
int val, cnt, size;
Node() {
val = cnt = size = ;
}
void update() {
Node *s = lson->cnt >= rson->cnt ? lson : rson;
val = s->val;
cnt = s->cnt;
size = lson->size + rson->size;
}
} *nil;
Node statePool[MAXT * ];
Node *stk[MAXT * ];
int top, scnt; Node* new_node() {
Node *p;
if(top) p = stk[--top];
else p = &statePool[scnt++];
p->lson = p->rson = nil;
p->val = p->cnt = p->size = ;
return p;
} void del_node(Node *p) {
stk[top++] = p;
} void remove(Node *y) {
if(y->lson != nil) remove(y->lson);
if(y->rson != nil) remove(y->rson);
del_node(y);
} void modify(Node *&x, int l, int r, int pos, int val) {
if(x == nil) x = new_node();
if(l == r) {
x->val = l;
x->cnt += val;
x->size = (x->cnt > );
} else {
if(pos <= mid) modify(x->lson, l, mid, pos, val);
if(mid < pos) modify(x->rson, mid + , r, pos, val);
x->update();
}
} void merge(Node *x, Node *y, int l, int r) {
if(y->size != ) {
if(l == r) {
modify(x, , maxz, l, y->cnt);
} else {
merge(x, y->lson, l, mid);
merge(x, y->rson, mid + , r);
}
}
} Node* merge(Node *x, Node *y) {
if(x->size < y->size) swap(x, y);
merge(x, y, , maxz);
remove(y);
return x;
} vector<PII> query[MAXV];
struct Modify {
int u, v, c, lca;
void read(int i) {
scanf("%d%d%d", &u, &v, &c);
maxz = max(maxz, c);
query[u].push_back(make_pair(v, i));
query[v].push_back(make_pair(u, i));
}
} ask[MAXV];
int fa[MAXV];
bool vis[MAXV]; int find_set(int x) {
return fa[x] == x ? x : fa[x] = find_set(fa[x]);
} void lca(int u, int f) {
for(int p = head[u]; ~p; p = next[p]) {
int &v = to[p];
if(v == f || vis[v]) continue;
lca(v, u);
fa[v] = u;
}
vis[u] = true;
for(vector<PII>::iterator it = query[u].begin(); it != query[u].end(); ++it) {
if(vis[it->first]) {
ask[it->second].lca = find_set(it->first);
}
}
} vector<PII> pre[MAXV], nxt[MAXV];
int ans[MAXV]; Node* dfs(int u, int f) {
Node *x = new_node();
for(int p = head[u]; ~p; p = next[p]) {
int v = to[p];
if(v == f) continue;
x = merge(x, dfs(v, u));
}
for(vector<PII>::iterator it = pre[u].begin(); it != pre[u].end(); ++it)
modify(x, , maxz, it->first, it->second);
ans[u] = x->val;
for(vector<PII>::iterator it = nxt[u].begin(); it != nxt[u].end(); ++it)
modify(x, , maxz, it->first, it->second);
return x;
} void solve() {
for(int i = ; i <= n; ++i) {
fa[i] = i;
vis[i] = false;
pre[i].clear(); nxt[i].clear();
}
lca(, );
for(int i = ; i < m; ++i) {
const Modify &t = ask[i];
pre[t.u].push_back(make_pair(t.c, ));
pre[t.v].push_back(make_pair(t.c, ));
pre[t.lca].push_back(make_pair(t.c, -));
nxt[t.lca].push_back(make_pair(t.c, -));
}
top = scnt = ;
Node *p = dfs(, );
if(p != nil) remove(p); for(int i = ; i <= n; ++i)
printf("%d\n", ans[i]);
} int main() {
nil = new Node();
nil->lson = nil->rson = nil; while(scanf("%d%d", &n, &m) != EOF) {
if(n == && m == ) break;
init();
for(int i = , u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
add_edge(u, v);
}
for(int i = ; i <= n; ++i) query[i].clear();
maxz = ;
for(int i = ; i < m; ++i) ask[i].read(i);
solve();
}
}
最新文章
- PHP 生成验证码
- php原型模式的研究
- JavaScript求和
- sublime学习
- 转	git使用命令, 特别:git checkout -b a 与 git branch a区别
- form作为module name 悲剧了
- 【svn】 SVN错误:Attempted to lock an already-locked dir
- 在windows下添加php的Imagick扩展
- locate: can not stat () `/var/lib/mlocate/mlocate.db&#39;: No such file or directory
- 老李分享:https协议
- Python安装与环境变量的配置
- R语言-图的要素颜色
- 机器学习技法笔记:12 Neural Network
- javascript篇-typeof,instanceof,constructor,toString判断数据类型的用法和区别
- gitlab 部署
- Expo大作战(三)--针对已经开发过react native项目开发人员有针对性的介绍了expo,expo的局限性,开发时项目选型注意点等
- 20155234《网路对抗》Exp9 WEB安全基础
- linux下如何模拟按键输入和模拟鼠标【转】
- Android MD5校验码的生成与算法实现
- Java 訪问权限控制:你真的了解 protected keyword吗?