首页 技术 正文
技术 2022年11月23日
0 收藏 764 点赞 2,190 浏览 3124 个字

题目来源:POJ 2763 Housewife Wind

题意:给你一棵树 2种操作0 x 求当前点到x的最短路 然后当前的位置为x; 1 i x 将第i条边的权值置为x

思路:树上两点u, v距离为d[u]+d[v]-2*d[LCA(u,v)] 如今d数组是变化的 相应每一条边的变化 他改动的是一个区间 用时间戳处理每个点管辖的区域 然后用线段树改动 线段树的叶子节点村的是根到每个点的距离 求近期公共祖先没区别 仅仅是堕落用线段树维护d数组

各种错误 4个小时 伤不起

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200010;
struct edge
{
int u, v, w, next;
}edges[maxn*2], e[maxn];int E[maxn*2], H[maxn*2], I[maxn*2], L[maxn], R[maxn];
int dp[maxn*2][40];
int cnt, clock, dfn;
int first[maxn];
int a[maxn<<2];
int b[maxn];
int add[maxn<<2];
int degree[maxn];
int vis[maxn];
void AddEdge(int u, int v, int w)
{
edges[cnt].u = u;
edges[cnt].v = v;
edges[cnt].w = w;
edges[cnt].next = first[u];
first[u] = cnt++;
edges[cnt].u = v;
edges[cnt].v = u;
edges[cnt].w = w;
edges[cnt].next = first[v];
first[v] = cnt++;
}
void dfs(int u, int fa, int dep)
{
E[++clock] = u;
H[clock] = dep;
I[u] = clock;
L[u] = ++dfn;
b[dfn] = u;
for(int i = first[u]; i != -1; i = edges[i].next)
{
int v = edges[i].v;
if(v == fa)
continue;
if(vis[v])
continue;
vis[v] = true;
dfs(v, u, dep+1);
E[++clock] = u;
H[clock] = dep;
}
R[u] = dfn;
}void RMQ_init(int n)
{
for(int i = 1; i <= n; i++)
dp[i][0] = i;
for(int j = 1; (1<<j) <= n; j++)
for(int i = 1; i+(1<<j)-1 <= n; i++)
{
if(H[dp[i][j-1]] < H[dp[i+(1<<(j-1))][j-1]])
dp[i][j] = dp[i][j-1];
else
dp[i][j] = dp[i+(1<<(j-1))][j-1];
}
}
int RMQ(int l, int r)
{
l = I[l], r = I[r];
if(l > r)
swap(l, r);
int len = r-l+1, k = 0;
while((1<<k) <= len)
k++;
k--;
if(H[dp[l][k]] < H[dp[r-(1<<k)+1][k]])
return E[dp[l][k]];
else
return E[dp[r-(1<<k)+1][k]];
}
void pushdown(int rt, int l, int r)
{
int k = (r-l+1);
if(add[rt])
{
a[rt<<1] += add[rt]*(k-(k>>1));
a[rt<<1|1] += add[rt]*(k>>1);
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
add[rt] = 0;
}
}void build(int l, int r, int rt)
{
a[rt] = 0;
add[rt] = 0;
if(l == r)
return;
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
}void update(int x, int y, int l, int r, int rt, int num)
{
if(l == x && r == y)
{
a[rt] += (r-l+1)*num;
add[rt] += num;
return;
}
pushdown(rt, l, r);
int m = (l + r) >> 1;
if(y <= m)
update(x, y, l, m, rt<<1, num);
else if(x > m)
update(x, y, m+1, r, rt<<1|1, num);
else
{
update(x, m, l, m, rt<<1, num);
update(m+1, y, m+1, r, rt<<1|1, num);
}
a[rt] = a[rt<<1] + a[rt<<1|1];
}int query(int x, int l, int r, int rt)
{
if(l == r)
{
return a[rt];
}
pushdown(rt, l, r);
int m = (l + r) >> 1;
int ans = 0;
if(x <= m)
ans = query(x, l, m, rt<<1);
else
ans = query(x, m+1, r, rt<<1|1);
a[rt] = a[rt<<1] + a[rt<<1|1];
return ans;
}
int main()
{
int cas = 1;
int T;
//scanf("%d", &T);
int s, to, root, n, q;
while(scanf("%d %d %d", &n, &q, &s) != EOF)
{
memset(vis, 0, sizeof(vis));
memset(first, -1, sizeof(first));
memset(degree, 0, sizeof(degree));
clock = cnt = dfn = 0;build(1, n, 1);
//for(int i = 1; i <= n; i++)
//scanf("%d", &b[i]);
for(int i = 1; i < n; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
e[i].u = u;
e[i].v = v;
e[i].w = w;
AddEdge(u, v, 0);
degree[v]++;
}for(int i = 1; i <= n; i++)
if(!degree[i])
{
vis[i] = true;
dfs(i, -1, 0);
root = i;
break;
}
RMQ_init(2*n-1);
//puts("1");
for(int i = 1; i < n; i++)
{
int u = e[i].u;
int v = e[i].v;
int w = e[i].w;
//printf("***%d %d\n", L[v], R[v]);
if(L[u] < L[v])
update(L[v], R[v], 1, n, 1, w);
else
update(L[u], R[u], 1, n, 1, w);
}while(q--)
{
int x;
scanf("%d", &x);
if(!x)
{
scanf("%d", &to);
int d1 = query(L[s], 1, n, 1);
int d2 = query(L[to], 1, n, 1);
int lca = RMQ(s, to);
int d3 = query(L[lca], 1, n, 1);
//printf("***%d %d %d\n", d1, d2, d3);
printf("%d\n", d1+d2-2*d3);
//printf("%d\n", dfn);
s = to;
}
else
{
int i, w;
scanf("%d %d", &i, &w);
int x = w - e[i].w;
e[i].w = w;
int v = e[i].v;
int u = e[i].u;
if(L[u] < L[v])
update(L[v], R[v], 1, n, 1, x);
else
update(L[u], R[u], 1, n, 1, x);
}
}
}
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141447.html

下一篇: URAL 1807
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,091
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,509
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,315
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站