边权转点权,每次遍历到下一个点,把走个这条边的权值加入主席树中即可。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxx = 2e5+;
struct node{
int l,r,cnt;
}tree[maxx*];
int head[maxx],rk[maxx],siz[maxx],top[maxx],son[maxx],d[maxx],fa[maxx],id[maxx],rt[maxx];
int dis[maxx];
struct Edge{
int Next,to,w;
}edge[maxx<<];
int root[maxx];
int tot=,cnt=,order;
void inserts(int l,int r,int pre,int &now,int pos){
now=++cnt;
tree[now]=tree[pre];
tree[now].cnt++;
if (l==r){
return ;
}
int mid=(l+r)>>;
if (pos<=mid){
inserts(l,mid,tree[pre].l,tree[now].l,pos);
}else {
inserts(mid+,r,tree[pre].r,tree[now].r,pos);
}
}
int query(int L,int R,int l,int r,int w){
if (l==r){
return tree[R].cnt-tree[L].cnt;
}
int mid=(l+r)>>;
if (w<=mid){
return query(tree[L].l,tree[R].l,l,mid,w);
}else {
return tree[tree[R].l].cnt-tree[tree[L].l].cnt+query(tree[L].r,tree[R].r,mid+,r,w);
}
}
void add(int x,int y,int z){
edge[++tot].to=y;
edge[tot].w=z;
edge[tot].Next=head[x];
head[x]=tot;
}
void dfs1(int u,int f,int depth){
d[u]=depth;
fa[u]=f;
siz[u]=;
for (int i=head[u];i;i=edge[i].Next){
int v=edge[i].to;
if (v==f)continue;
dfs1(v,u,depth+);
dis[v]=edge[i].w;
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
id[u]=++order;
rk[order]=u;
// cout<<dis[u]<<endl;
inserts(,1e9,root[order-],root[order],dis[u]);
if(!son[u])return;
dfs2(son[u],t);
for (int i=head[u];i;i=edge[i].Next)
{
int v=edge[i].to;
if(v!=son[u] && v!=fa[u])
dfs2(v,v);
}
}
int query_line(int a,int b,int c){
int ans=;
while(top[a]!=top[b]){
if (d[top[a]]>d[top[b]])swap(a,b);
ans+=query(root[id[top[b]]-],root[id[b]],,1e9,c);
b=fa[top[b]];
}
if (d[a]>d[b])swap(a,b);
ans+=query(root[id[a]],root[id[b]],,1e9,c);
return ans;
}
int main(){
int w,op,n,uu,vv;
scanf("%d%d",&n,&op);
tot=;
cnt=;
order=;
for (int i=;i<n;i++){
scanf("%d%d%d",&uu,&vv,&w);
add(uu,vv,w);
add(vv,uu,w);
}
dfs1(,,);
dfs2(,);
// cout<<endl;
// for (int i=1;i<=n;i++){
// cout<<dis[i]<<"--";
// }
// cout<<endl;
// cout<<endl;
// for (int i=1;i<=n;i++){
// cout<<"--"<<id[i]<<endl;
// }
while(op--){
scanf("%d%d%d",&uu,&vv,&w);
printf("%d\n",w?query_line(uu,vv,w):);
}
return ;
}

最新文章

  1. [ActionScript 3.0] 对代码加密的有效方法
  2. 从源码角度理清memcache缓存服务
  3. 获取MAC地址的几种方式
  4. 【Bootstrap基础学习】02 Bootstrap的布局组件应用示例
  5. heaters
  6. ajax 方法解密
  7. sscanf和sprintf是scanf和printf家族用法 (转)
  8. JavaScript网站设计实践(七)编写最后一个页面 改进表单
  9. 采用OSChina代码托管管理项目(一)
  10. [Android学习笔记]Android中多线程开发的一些概念
  11. [POJ 3150] Cellular Automaton (矩阵高速幂 + 矩阵乘法优化)
  12. line-height:2、line-height:2em、line-height:200%的区别
  13. [ An Ac a Day ^_^ ] CodeForces 468A 24 Game 构造
  14. JAVA课设个人博客--多源数据教学管理系统
  15. EOS.IO Technical White Paper v2
  16. python使用dns轮循检测web服务器是否异常
  17. AT&amp;T汇编和Intel汇编语法主要区别
  18. bzoj2662
  19. cf478B-Random Teams 【排列组合】
  20. Intent对象若干数据项的含义总结

热门文章

  1. LINNX查看当前登录的用户
  2. hdu 1296 Polynomial Problem(多项式模拟)
  3. tinkcmf视频上传大小限制
  4. mybatis官网文档mybatis_doc
  5. python通过http(multipart/form-data)上传文件的方法
  6. Python单元测试浅析
  7. Spring Boot → 11:项目实战-账单管理系统完整版
  8. Codeforces Round #410 (Div. 2) A. Mike and palindrome【判断能否只修改一个字符使其变成回文串】
  9. DirectX11笔记(四)--渲染管线
  10. Leetcode860.Lemonade Change柠檬水找零