HDU5840(SummerTrainingDay08-B 树链剖分+分块)
This world need more Zhu
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 454 Accepted Submission(s): 84
Problem Description
In Duoladuo, this place is like a tree. There are n vertices and n−1 edges. And the root is 1. Each vertex can reached by any other vertices. Each vertex has a people with value Ai named Zhu's believer.
Liao is a curious baby, he has m questions to ask Zhu. But now Zhu is busy, he wants you to help him answer Liao's questions.
Liao's question will be like "u v k".
That means Liao want to know the answer from following code:
ans = 0; cnt = 0;
for x in the shortest path from u to v {
cnt++;
if(cnt mod k == 0) ans = max(ans,a[x]);
}
print(ans).
Please read the hints for more details.
Input
In the second line there are two numbers n, m. n is the size of Duoladuo, m is the number of Liao's questions.
The next line contains n integers A1,A2,...An, means the value of ith vertex.
In the next n−1 line contains tow numbers u, v. It means there is an edge between vertex u and vertex v.
The next m lines will be the Liao's question:
u v k
1≤T≤10,1≤n≤100000,1≤m≤100000,1≤u,v≤n,1≤k, Ai≤1000000000.
Output
Then, you need to output the answer for every Liao's questions.
Sample Input
5 5
1 2 4 1 2
1 2
2 3
3 4
4 5
1 1 1
1 3 2
1 3 100
1 5 2
1 3 1
Sample Output
1
2
0
2
4
Hint
In query 1,there are only one vertex in the path,so the answer is 1.
In query 2,there are three vertices in the path.But only the vertex 2 mod 2 equals to 0.
In query 3,there are three vertices in the path.But no vertices mod 100 equal to 0.
In query 4,there are five vertices in the path.There are two vertices mod 2 equal to 0.So the answer is max(a[2],a[4]) = 2.
In query 5,there are three vertices in the path.And all the vertices mod 1 equal to 0. So the answer is a[3] = 4.
Author
Source
//2017-08-08
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define lson (id<<1)
#define rson ((id<<1)|1) using namespace std; const int N = ;
const int LEN = ;//块的大小
vector<int> G[N];
int n, m, label, answer[N]; //树链剖分
int arr[N];//arr[i]表示节点i的权值
int fa[N];//fa[i]表示节点i的父亲
int son[N];//son[i]表示节点i的重儿子
int top[N];//top[i]表示节点i所在重链的顶端节点
int size[N];//size[i]表示以节点i为根的子树的节点数
int deep[N];//deep[i]表示节点i的深度
int postion[N];//postion[i]表示节点i在线段树中的位置
int trID[N];//trID[i]表示节点i在剖分后的新编号 void dfs1(int u, int father){
fa[u] = father;
son[u] = ;
size[u] = ;
for(auto v: G[u]){
if(v == father)continue;
deep[v] = deep[u]+;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]])
son[u] = v;
}
} void dfs2(int u, int ancestor){
top[u] = ancestor;
postion[u] = ++label;
trID[label] = u;
if(son[u])
dfs2(son[u], ancestor);
for(auto v: G[u]){
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
} //最近公共祖先
inline int lca(int u, int v){
while(top[u] ^ top[v]){
if(deep[top[u]] < deep[top[v]])
swap(u, v);
u = fa[top[u]];
}
return deep[u] < deep[v] ? u : v;
} //线段树
struct Node{
int l, r, v;
}tree[N<<];
int nS[N], qL[N], qR[N]; void build(int id, int l , int r){
tree[id].l = l;
tree[id].r = r;
if(l == r){
tree[id].v = arr[trID[nS[l]]];
return;
}
int mid = (l+r)>>;
build(lson, l, mid);
build(rson, mid+, r);
tree[id].v = max(tree[lson].v, tree[rson].v);
} int query(int id, int l, int r){
if(tree[id].l == l && tree[id].r == r)
return tree[id].v;
int mid = (tree[id].l+tree[id].r)>>;
if(l > mid)return query(rson, l, r);
if(r <= mid)return query(lson, l, r);
return max(query(lson, l, mid), query(rson, mid+, r));
} inline int cal(int l, int r, int k){
if(qL[k] > qR[k])return ;
l = lower_bound(nS+qL[k], nS+qR[k]+, l)-nS;
r = upper_bound(nS+qL[k], nS+qR[k]+, r)-nS-;
if(l <= r)return query(, l, r);
else return ;
} int question(int u, int v, int k){
int ans = -, f = lca(u, v);
int uk = (deep[u] + )%k;
int vk = (deep[f] + (k - (deep[u]-deep[f]+)%k)) % k;
while(top[u] ^ top[v]){
if(deep[top[u]] > deep[top[v]]){
ans = max(ans, cal(postion[top[u]], postion[u], uk));
u = fa[top[u]];
}else{
ans = max(ans, cal(postion[top[v]], postion[v], vk));
v = fa[top[v]];
}
}
if(deep[u] > deep[v])
ans = max(ans, cal(postion[v], postion[u], uk));
else
ans = max(ans, cal(postion[u], postion[v], vk));
return ans;
} vector<int> block[LEN];
vector< pair< pair<int, int>, int > > qs[LEN+];
vector< pair< pair<int, int>, pair<int, int> > > qy[N];
void solve(int k){
for(int i = ; i <= n; i++){
int u = trID[i];
block[deep[u]%k].push_back(u);
}
label = ;
for(int i = ; i < k; i++){
qL[i] = label + ;
for(auto x: block[i])
nS[++label] = postion[x];
qR[i] = label;
}
build(, , n);
for(auto &x: qs[k])
answer[x.second] = question(x.first.first, x.first.second, k);
for(int i = ; i < k; i++)
block[i].clear();
qs[k].clear();
} int sk[N], tp;//sk为栈, tp为栈顶指针 void dfs(int u){
sk[++tp] = u;
for(auto &x: qy[u]){
for(int i = tp-x.first.second;
i > && deep[sk[i]] >= deep[x.first.first];
i -= x.second.first)
answer[x.second.second] = max(answer[x.second.second], arr[sk[i]]);
}
qy[u].clear();
for(auto v : G[u]){
if(v ^ fa[u])
dfs(v);
}
--tp;
} int main()
{
//freopen("dataB.txt", "r", stdin);
int T, kase = ;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
scanf("%d", &arr[i]);
int u, v, k;
for(int i = ; i <= n; i++)
G[i].clear();
for(int i = ; i <= n-; i++){
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
label = ;
dfs1(, );
dfs2(, );
//debug();
for(int i = ; i < m; i++){
scanf("%d%d%d", &u, &v, &k);
if(k >= LEN){
int f = lca(u, v);
int d = (deep[u]+deep[v]-*deep[f]+)%k;
if(u ^ f)
qy[u].push_back({ {f, k-}, {k, i} });
if(v ^ f)
qy[v].push_back({ {f, d}, {k, i} });
}else{
qs[k].push_back({ {u, v}, i });
}
}
memset(answer, , sizeof(answer));
for(int i = ; i < LEN; i++)
if(qs[i].size())
solve(i);
tp = ;
dfs();
printf("Case #%d:\n", ++kase);
for(int i = ; i < m; i++)
printf("%d\n", answer[i]);
} return ;
}
最新文章
- 基于HTML5树组件延迟加载技术实现
- MVC:Control与View传值
- Unity 协程与线程
- BZOJ4310 : 跳蚤
- 【JEMTER】后置处理器JSON Path Extractor获取server端返回的json中某项值
- UVa 10465 Homer Simpson (枚举)
- sencha app build 到 Capturing theme image不执行
- JBoss AS 7性能调优(三)
- Subsets 【dfs】
- 依赖注入容器Autofac与MVC集成
- C++traits——STL源码剖析
- 实验:利用ASMLib创建ASM磁盘
- 关于for循环里面异步操作的问题
- 第三讲 smart qq 登录成功后获取 vfwebqq ,psessionid,hash
- 关系测试# 或 print(s2-s)Python 集合
- Flask学习-前言
- 两种常用文件分享方式 - 网络硬盘快速分享, 点对点的文件共享 BitTorrent Sync
- Visual Studio 2017 如何 监控当前变量 占用内存空间大小
- array_diff使用注意
- DML操纵语句