POJ 2763 树链剖分 线段树 Housewife Wind
2024-09-29 21:45:39
单个边的权值修改以及询问路径上的权值之和。
数据量比较大,用vector存图会超时的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; void scan(int& x)
{
x = ;
int ch = ' ';
while(ch < '' || ch > '') ch = getchar();
while(ch >= '' && ch <= '') { x = x * + ch - ''; ch = getchar(); }
} int n, Q, s; const int maxn = + ;
int u[maxn], v[maxn], d[maxn]; struct Edge
{
int v, nxt;
}; int cnt;
int head[maxn];
Edge edge[maxn * ]; void AddEdge(int u, int v)
{
edge[cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt++;
} int tot;
int L[maxn];
int fa[maxn];
int sz[maxn];
int son[maxn];
int id[maxn];
int top[maxn]; void dfs(int u)
{
sz[u] = ; son[u] = ;
for(int i = head[u]; i != -; i = edge[i].nxt)
{
int v = edge[i].v;
if(v == fa[u]) continue;
fa[v] = u;
L[v] = L[u] + ;
dfs(v);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
} void dfs2(int u, int tp)
{
top[u] = tp;
if(son[u]) { id[son[u]] = ++tot; dfs2(son[u], tp); }
for(int i = head[u]; i != -; i = edge[i].nxt)
{
int v = edge[i].v;
if(v == fa[u] || v == son[u]) continue;
id[v] = ++tot;
dfs2(v, v);
}
} int sum[maxn << ]; void update(int o, int L, int R, int p, int v)
{
if(L == R) { sum[o] = v; return ; }
int M = (L + R) / ;
if(p <= M) update(o<<, L, M, p, v);
else update(o<<|, M+, R, p, v);
sum[o] = sum[o<<] + sum[o<<|];
} int query(int o, int L, int R, int qL, int qR)
{
if(qR < L || qL > R) return ;
if(qL <= L && R <= qR) return sum[o];
int ans = ;
int M = (L + R) / ;
ans += query(o<<, L, M, qL, qR);
ans += query(o<<|, M+, R, qL, qR);
return ans;
} int Query(int u, int v)
{
int ans = ;
int t1 = top[u], t2 = top[v];
while(t1 != t2)
{
if(L[t1] < L[t2]) { swap(u, v); swap(t1, t2); }
ans += query(, , tot, id[t1], id[u]);
u = fa[t1]; t1 = top[u];
}
if(u == v) return ans;
if(L[u] < L[v]) swap(u, v);
ans += query(, , tot, id[son[v]], id[u]);
return ans;
} int main()
{
while(scanf("%d%d%d", &n, &Q, &s) == )
{
memset(head, -, sizeof(head));
cnt = ;
for(int i = ; i < n; i++)
{
scan(u[i]); scan(v[i]); scan(d[i]);
AddEdge(u[i], v[i]);
AddEdge(v[i], u[i]);
} L[] = fa[] = ;
dfs();
tot = ;
dfs2(, ); memset(sum, , sizeof(sum));
for(int i = ; i < n; i++)
{
if(L[u[i]] < L[v[i]]) swap(u[i], v[i]);
update(, , tot, id[u[i]], d[i]);
} int op, x, y;
while(Q--)
{
scan(op);
if(op == )
{
scan(x);
printf("%d\n", Query(s, x));
s = x;
}
else
{
scan(x); scan(y);
update(, , tot, id[u[x]], y);
}
}
} return ;
}
代码君
最新文章
- Google的Java常用类库 Guava资料
- MySQL(七) —— MySQL存储过程 &; 存储引擎
- sql_查询select
- http://www.ibm.com/developerworks/cn/java/j-lo-hotswapcls/
- Android 之 自定义标签 和 自定义组件
- mapreduce的基本思想
- BZOJ 3236: [Ahoi2013]作业( 莫队 + BIT )
- BMP文件结构
- UOJ #5. 【NOI2014】动物园 扩大KMP
- 寒假学干货之------ 初学者关于fragment_main(碎片的困扰)
- 基于Jmeter的接口自动化测试实践
- python3 Tkinter GUI 试水
- [转帖]windows+xshell+xming访问非桌面版Linux服务器
- 如何查找物理cpu,cpu核心和逻辑cpu的数量
- 存储过程导入excel
- 第 3 章 镜像 - 013 - Dockerfile 构建镜像
- 基于oslo_log的日志管理
- Python vars() 函数
- [洛谷P2057][bzoj1934]善意的投票(最大流)
- 运行用例时,报错Unknow Error:Element xxx is not clickable……的解决方法