题意:给出一棵树,给出每条边的权值,现在给出m个询问,要你每次输出u~v的最短路径中,边权 <= k 的边有几条

思路:当时网络赛的时候没学过主席树,现在补上。先树上建主席树,然后把边权交给子节点,然后数量就变成了 u + v - lca * 2。专题里那道算点权的应该算原题吧。1A = =,强行做模板题提高自信。

代码:

#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
const int M = maxn * 30;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int n, m;
int root[maxn], tot;
struct Edge{
int v, next;
ll w;
}edge[maxn << 1];
int head[maxn], tol;
void addEdge(int u, int v, ll w){
edge[tol].v = v;
edge[tol].w = w;
edge[tol].next = head[u];
head[u] = tol++;
}
struct node{
int lson, rson;
int sum;
}T[maxn * 40];
void init(){
memset(T, 0, sizeof(T));
memset(root, 0, sizeof(root));
memset(head, -1, sizeof(head));
tot = tol = 0;
}
vector<int> vv;
int getid(int x){
return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + 1;
}
void update(int l, int r, int &now, int pre, int v, int pos){
T[++tot] = T[pre], T[tot].sum += v, now = tot;
if(l == r) return;
int m = (l + r) >> 1;
if(pos <= m)
update(l, m, T[now].lson, T[pre].lson, v, pos);
else
update(m + 1, r, T[now].rson, T[pre].rson, v, pos);
}
void build(int now, int pre, ll w){
update(1, vv.size(), root[now], root[pre], 1, getid(w));
for(int i = head[now]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(v == pre) continue;
build(v, now, edge[i].w);
}
}
int query(int l, int r, int now, int pre, int lca, int k){
if(l == r){
if(k >= l) return T[now].sum + T[pre].sum - T[lca].sum * 2;
return 0;
}
if(r <= k) return T[now].sum + T[pre].sum - T[lca].sum * 2;
int m = (l + r) >> 1;
int sum = 0;
if(k <= m)
return query(l, m, T[now].lson, T[pre].lson, T[lca].lson, k);
else{
sum = query(m + 1, r, T[now].rson, T[pre].rson, T[lca].rson, k);
return sum + T[T[now].lson].sum + T[T[pre].lson].sum - T[T[lca].lson].sum * 2;
}
} //lca
int fa[maxn][20];
int dep[maxn];
void lca_dfs(int u, int pre, int d){
dep[u] = d;
fa[u][0] = pre;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(v != pre)
lca_dfs(v, u, d + 1);
}
}
void lca_update(){
for(int i = 1; (1 << i) <= n; i++){
for(int u = 1; u <= n; u++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
}
}
int lca_query(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int i = 0; (1 << i) <= d; i++){
if(d & (1 << i)){
u = fa[u][i];
}
}
if(u != v){
for(int i = (int)log2(n); i >= 0; i--){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
u = fa[u][0];
}
return u;
}
int u1[maxn], v1[maxn];
ll k1[maxn];
int main(){
init();
vv.clear();
scanf("%d%d", &n, &m);
vv.push_back(0);
for(int i = 1; i <= n - 1; i++){
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
vv.push_back(w);
}
for(int i = 1; i <= m; i++){
scanf("%d%d%lld", &u1[i], &v1[i], &k1[i]);
vv.push_back(k1[i]);
}
sort(vv.begin(), vv.end());
vv.erase(unique(vv.begin(), vv.end()), vv.end());
lca_dfs(1, 0, 1);
lca_update();
build(1, 0, 0);
for(int i = 1; i <= m; i++){
int lca = lca_query(u1[i], v1[i]);
printf("%d\n", query(1, vv.size(), root[u1[i]], root[v1[i]], root[lca], getid(k1[i])));
}
return 0;
}

最新文章

  1. Si2155
  2. Java集合之泛型的使用
  3. VS 打开工程后 自动关闭
  4. Some Simple Models of Neurons
  5. 菜鸟调错(八)—— Maven编译错误:不兼容的类型的解决方案
  6. arm-linux-gcc 常用参数讲解 gcc编译器使用方法
  7. Java 图片提取RGB数组 RGBOfCharMaps (整理)
  8. 海明距离hamming distance
  9. css3绘制中国结
  10. 网站全局js代码
  11. StrPCopy与StrPas功能正好相反,作用是与C语言字符串和Delphi的String相互转化
  12. OpenStack high-level Functionsenabled
  13. springMVC注解优化
  14. Linux负载均衡软件LVS之二(安装篇)
  15. 了解Scala反射
  16. Android系统裁剪:手把手教你如何进行系统裁剪
  17. spring boot jpa 整合
  18. @RequestParam、@ReqeustBody、@ReponseBody认识
  19. Beautiful Paintings CodeForces - 651B (贪心)
  20. vue 列表选中 v-for class

热门文章

  1. win32 修改Edit控件文本颜色与背景色
  2. Linux学习安装
  3. (15)-Python3之--configparser模块
  4. 【转载】【网络安全】渗透中 PoC、Exp、Payload 与 Shellcode 的区别
  5. TCP/IP建立连接的时候ISN序号分配问题
  6. Treap——堆和二叉树的完美结合,性价比极值的搜索树
  7. Smarty 3.1.34 反序列化POP链(任意文件删除)
  8. Node 使用webpack编写简单的前端应用
  9. Web下无插件播放rtsp视频流的方案及各家优秀内容资源整理
  10. 数字转金额格式* 999999.99 TO 999,999.99