一、前言

  这破题WA了一天,最后重构还是WA,最后通过POJ讨论版得到的数据显示,我看上去是把某个变量写错了。。于是,还是低级错误背锅啊。。。。代码能力有待进一步提升2333333

二、题意

  某家庭主妇住在一棵树上,他的若干个孩子在树的若干个节点上有分布,主妇同学需要从某给定节点出发,飞到树上的制定节点,在过程中,边权可能会发生改变,问从当前节点到指定节点的边权和。

三、解法

  树链拋分,点更新查区间。

// #include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std; #define ll long long
#define pp pair<int ,int> const ll MAXN=1e5+; class Node
{
public:
int next,to,cost;
void init(int a,int b,int c)
{
this->next=a;
this->to=b;
this->cost=c;
}
};
Node G[MAXN*];
int tree[MAXN],child[MAXN],deep[MAXN],number[MAXN],top[MAXN],points[MAXN],father[MAXN];
int size,summ,n,q,s;
void insert(int pos,int key)
{
while(pos<MAXN)
{
tree[pos]+=key;
pos+=pos&(-pos);
}
}
int getSum(int pos)
{
int ans=;
while(pos)
{
ans+=tree[pos];
pos-=pos&(-pos);
}return ans;
}
void add(int from,int to,int cost)
{
G[summ].init(points[from],to,cost);
points[from]=summ++;
}
void dfs_1(int now,int last,int dep)
{
deep[now]=dep;
father[now]=last;
child[now]=;
for(int i=points[now];i!=-;i=G[i].next)
{
int tar=G[i].to;
int cost=G[i].cost;
if(tar==last)continue;
dfs_1(tar,now,dep+);
child[now]+=child[tar];
}
}
void dfs(int now,int last,int first,int cc=)
{
top[now] = first ? first : now;
insert(size,cc);
// cout<<"check_number: "<<now<<ends<<size<<endl;
number[now]=size++;
int maxx,pos,coS;
maxx=pos=-;
for(int i=points[now];i!=-;i=G[i].next)
{
int tar=G[i].to;
int cost=G[i].cost;
if(tar==last)continue;
if(maxx<child[tar])
{
maxx=child[tar];
pos=tar;
coS=cost;
}
}if(pos!=-)dfs(pos,now,top[now],coS);
for(int i=points[now];i!=-;i=G[i].next)
{
int tar=G[i].to;
int cost=G[i].cost;
if(tar==last||tar==pos)continue; dfs(tar,now,,cost);
}
}
void update(int num,int key)
{
int a=G[num*].to;
int b=G[num*+].to;
if(father[a]==b)
{
key=key-(getSum(number[a])-getSum(number[a]-));
insert(number[a],key);
}else
{
key=key-(getSum(number[b])-getSum(number[b]-));
insert(number[b],key);
}
}
int query(int from,int to)
{
int ans=;
int t1=top[from];
int t2=top[to];
// cout<<"check_top: "<<t1<<ends<<t2<<endl;
// cout<<"check_point: "<<from<<ends<<to<<endl;
while(t1!=t2)
{
if(deep[t1]<deep[t2])
{
swap(t1,t2);
swap(from,to);
}
ans+=getSum(number[from])-getSum(number[t1]-);
from=father[t1];
t1=top[from];
}
int star=min(number[from],number[to]);
int endd=max(number[from],number[to]);
// cout<<ans<<"check_Number: "<<star<<ends<<endd<<endl;
// cout<<"checkSum: "<<getSum(endd)<<ends<<getSum(star)<<endl;
ans+=getSum(endd)-getSum(star);
return ans;
}
void init()
{
size=;summ=;
memset(points,-,sizeof(points));
for(int i=;i<n;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
// cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}dfs_1(,,);
dfs(,,);
for(int i=;i<q;++i)
{
int a,b,c;
// cin>>c;
scanf("%d",&c);
if(c)
{
// cin>>a>>b;
scanf("%d%d",&a,&b);
a--;
update(a,b);
}else{
// cin>>a;
scanf("%d",&a);
cout<<query(s,a)<<"\n";
s=a;
}
}
} int main()
{
// cin.sync_with_stdio(false);
cin>>n>>q>>s;init(); return ;
}

最新文章

  1. linux基础知识与技能1
  2. UliPad ----python 开发利器
  3. [游戏模版11] Win32 动画 时间消息
  4. .NET Core创建一个控制台(Console)程序
  5. Spring 事物机制
  6. 【NOIP2010】【P1317】乌龟棋
  7. JapserReport导出PDF Could not load the following font错误
  8. Table of Contents - Quartz Scheduler
  9. 【学习笔记】【C语言】sizeof
  10. LA 3641 (置换 循环的分解) Leonardo&#39;s Notebook
  11. JQuery 之 Ajax 异步和同步浅谈
  12. 05顺序队列_Queue--(栈与队列)
  13. java的一些程序
  14. CSS.01 -- 选择器及相关的属性文本、文字、字体、颜色、
  15. 在Github上面搭建一个自己域名的Hexo博客
  16. Spring Boot入门(二):使用Profile实现多环境配置管理&amp;如何获取配置文件值
  17. 深度学习Tensorflow生产环境部署(上&#183;环境准备篇)
  18. CLOUD物料列表查询的一份跟踪
  19. Kafka集群管理工具kafka-manager的安装使用
  20. Linux之文件(目录)默认权限、特殊权限与隐藏权限

热门文章

  1. 北航oo作业第三单元小结
  2. Java项目—嗖嗖移动业务大厅
  3. 从零开始的全栈工程师——js篇2.11(原型)
  4. 第6章 传输层(详解TCP的三次握手与四次挥手)
  5. System Center Configuration Manager 2016 必要条件准备篇(Part1)
  6. Extjs4.1+desktop+SSH2 定义程序入口
  7. 【BZOJ2006】[NOI2010] 超级钢琴(堆+RMQ)
  8. python基础一 day17 作业
  9. 19课 Vue第二节
  10. Python求列表中某个元素的下标