POJ 2763 Housewife Wind(树链剖分)(线段树单点修改)
Time Limit: 4000MS | Memory Limit: 65536K | |
Total Submissions: 10378 | Accepted: 2886 |
Description
Since Jiajia earned enough money, Wind became a housewife. Their
children loved to go to other kids, then make a simple call to Wind:
'Mummy, take me home!'
At different times, the time needed to walk along a road may be
different. For example, Wind takes 5 minutes on a road normally, but may
take 10 minutes if there is a lovely little dog to play with, or take 3
minutes if there is some unknown strange smell surrounding the road.
Wind loves her children, so she would like to tell her children the exact time she will spend on the roads. Can you help her?
Input
first line contains three integers n, q, s. There are n huts in XX
Village, q messages to process, and Wind is currently in hut s. n <
100001 , q < 100001.
The following n-1 lines each contains three integers a, b and w.
That means there is a road directly connecting hut a and b, time
required is w. 1<=w<= 10000.
The following q lines each is one of the following two types:
Message A: 0 u
A kid in hut u calls Wind. She should go to hut u from her current position.
Message B: 1 i w
The time required for i-th road is changed to w. Note that the
time change will not happen when Wind is on her way. The changed can
only happen when Wind is staying somewhere, waiting to take the next
kid.
Output
Sample Input
3 3 1
1 2 1
2 3 2
0 2
1 2 3
0 3
Sample Output
1
3 树链剖分水题。建议在POJ上用C++交,用G++可能会超时。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int N=2e5+;
const int M=N*N+;
int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N]; //top 最近的重链父节点
int num,s,m,n,q;
int sum[N*],tre[*N];
vector<int> v[N];
struct tree {
int x,y,val;
void read() {
scanf("%d%d%d",&x,&y,&val);
}
}e[N];
void dfs1(int u, int f, int d) {
dep[u] = d;
siz[u] = ;
son[u] = ;
fa[u] = f;
for (int i = ; i < v[u].size(); i++) {
int ff = v[u][i];
if (ff == f) continue;
dfs1(ff, u, d + );
siz[u] += siz[ff];
if (siz[son[u]] < siz[ff])
son[u] = ff;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
id[u] = ++num;
if (son[u]) dfs2(son[u], tp);
for (int i = ; i < v[u].size(); i++) {
int ff = v[u][i];
if (ff == fa[u] || ff == son[u]) continue;
dfs2(ff, ff);
}
}
inline void PushPlus(int rt) {
sum[rt]=sum[rt*]+sum[rt*+];
} void Build(int l,int r,int rt) {
if(l==r) {
sum[rt]=val[l];
return;
}
int m=(l+r)>>;
Build(lson);
Build(rson);
PushPlus(rt);
//printf("rt=%d sum[rt]=%d\n",rt,sum[rt]);
} void Update(int p,int add,int l,int r,int rt) {
if(l==r) {
sum[rt]=add;
return;
}
int m=(r+l)>>;
if(p<=m)Update(p,add,lson);
else Update(p,add,rson);
PushPlus(rt);
} int Query(int L,int R,int l,int r,int rt) {
if(L<=l&&r<=R)return sum[rt];
int m=(l+r)>>;
int ans=;
if(L<=m)ans+=Query(L,R,lson);
if(R>m)ans+=Query(L,R,rson);
return ans;
} int Yougth(int u, int v) {
int tp1 = top[u], tp2 = top[v];
int ans = ;
while (tp1 != tp2) {
if (dep[tp1] < dep[tp2]) {
swap(tp1, tp2);
swap(u, v);
}
ans += Query(id[tp1], id[u],,n,);
u = fa[tp1];
tp1 = top[u];
}
if (u == v) return ans;
if (dep[u] > dep[v]) swap(u, v);
ans += Query(id[son[u]], id[v],,n,);
return ans;
}
void Clear(int n) {
for(int i=; i<=n; i++)
v[i].clear();
}
int main() {
int u,vv,w;
scanf("%d%d%d",&n,&q,&s);
for(int i=; i<n; i++) {
e[i].read();
v[e[i].x].push_back(e[i].y);
v[e[i].y].push_back(e[i].x);
}
num = ;
dfs1(,,);
dfs2(,);
for (int i = ; i < n; i++) {
if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x, e[i].y);
val[id[e[i].x]] = e[i].val;
}
Build(,num,);
while(q--) {
int x;
scanf("%d",&x);
if(!x){
scanf("%d",&u);
printf("%d\n",Yougth(s,u));
s=u;
}
else {
scanf("%d%d",&u,&vv);
Update(id[e[u].x],vv,,n,);
}
}
Clear(n); return ;
}
最新文章
- SharePoint 2013常用开发工具分享
- JavaScript 深入了解基本类型和引用类型的值
- wtforms 使用
- posix and system V IPC
- Vim 练级攻略
- 2维特征Feature2D(转)
- Linux 内核 链表 的简单模拟(1)
- PS/2接口
- phpcms v9中模板标签使用及联动菜单
- Indy10.2.5的危险做法
- fopen()函数以";a+";方式打开一个不存在的文件后读写出现问题
- Spring Cloud微服务中网关服务是如何实现的?(Zuul篇)
- bootStrap table 和 JS 开发过程中遇到问题汇总
- C++11模版元编程
- EasyUI datagrid 查询、设置、提交 三
- 使用ServiceStack改造我们的项目
- Centos配置为驱动程序开发环境
- OpenGL入门程序四:颜色模式
- [翻译] 学习iOS开发的建议:如何从菜鸟到专家
- Ubuntu vi 上下左右变ABCD问题解决方法