题面
n 点 2n-2 条有向边, 数据先给一颗 1 为根的生成树边集, 边目录按两部分给出
1, 开始的 n-1 条边描述了一颗以 1 号点为根的生成树, 即每个点都可以由 1 号点 到达.
2, 接下来的 N-1 条边, 一定是从 i 到 1(2<=i<=N) 的有向边, 保证每个点都能到
然后给出除 1 外每个点到 1 的距离, q 次询问两个操作:
1 x w 将第 x 条边的边权修改为 w
2 u v 问 u v 最短距离
[输入格式] 第一行是 2 个整数 N,Q, 表示一共 N 个点 Q 次询问 接下来是 N-1 行, 每行 3 个整数 U,V,W, 表示了前 N-1 条边, u 到 v 的有向边 接下来 N-1 行, 每行 3 个整数 U,V,W, 描述了每个点到 1 号点的边, V==1 接下来是 Q 行, 表示 Q 次修改与询问
[输出格式] 若干行, 每行回答一次询问
20% 数据 没有修改 30% 数据 2<=N,Q<=1000 (其中有 10% 数据没有修改) 100% 数据 2<=N,Q<=100 000, 1 <= 边权 <= 1000,000
分析
首先注意到了 20% 无修改, 第一反应就想到了 lca, 因为 lca 的一大用处就是求树上两点距离
但是存在一个问题, 这不是一棵普通的树, 根据题意, 有两种边, 前 n-1 条边我们称为树边, 后 n-1 条边我们称为返祖边
无修改的情况下, 如果 u 是 v 的祖先, 那就是纯 lca 模板了, 关键在于如果 u 不是 v 祖先呢? 那 u 要通过返祖边回到根节点, 再从根节点走到 v. 但注意, u 不仅可以从自身的返祖边回去, 还可以从子树的返祖边回去, 所以在 lca 时需初始化出以 u 回到 1 节点的最小代价 (即对于去到整个子树每个节点的路径以及返祖的边综合起来求最小). 再加上 30% 的 1000 的数据 (遍历子树的每个点修改), 暴力轻松得 40 分
------------------------- 以下为正解 ------------------------------
首先我们在暴力的时候就考虑到了进行预处理从任意节点回根的最小代价, 但现在我们必须要修改了, 所以还要考虑从根到此节点的路径权值和.
定义 dis[u] 为从 1->u->1 的路径值. 把返祖边记为 rev[u], 则 1 到 u 的树上距离为 dis[u]-rev[u]
查询
则有两种情况: 1.u 还是 v 的祖先, 则答案是 (dis[v]-rev[v])-(dis[u]-rev[u]) // 两树边相减
2.u 不是 v 的祖先. 需要在 u 的子树中找出最小的 dis[k] 值, 则答案是 dis[k]-(dis[u]-rev[u])+(dis[v]-rev[v]) //u 返祖路径的值 + 从根到 v 的树边的值
根据上述思路, 我们可以试着分两类边修改.
如果是任意节点 u 的树边, 修改会影响到整棵子树的 dis[], 但是如果是返祖边只会影响 u 自己的 dis[].
思路大概告一段落
但在查询和修改过程中发现了一系列问题: 1, 需要维护子树的最小值. 2, 需要修改子树的 dis.
所以用线段树维护 dis, 并通过 dfs 序编号 (dfs 序中一棵子树的节点是连续的, 便于操作). 用 st[u] 记录以 u 为根的子树的开始的 dfs 序, ed[u] 为结束的节点 dfs 序
- #include<bits/stdc++.h>
- using namespace std;
- #define N 200000
- #define INF 0x7fffffff
- #define ll long long
- #define lc (p<<1)
- #define rc (p<<1|1)
- #define mid (t[p].l+t[p].r>>1)
- ll first[N],dep[N],dfn[N],st[N],ed[N],dis[N],rev[N],ux[N],vx[N],wx[N];
- ll fa[N][20];
- ll n,q,cnt,idx;
- struct email
- {
- ll u,v;
- ll w;
- ll nxt;
- }e[N*2];
- struct NSD
- {
- ll l,r;
- ll minx,lazy;
- }t[N*4];
- inline void pushnow(ll p,ll val)
- {
- t[p].lazy+=val;
- t[p].minx+=val;
- }
- inline void pushup(ll p)
- {
- t[p].minx=min(t[lc].minx,t[rc].minx);
- }
- inline void pushdown(ll p)
- {
- if(t[p].lazy)
- {
- pushnow(lc,t[p].lazy);
- pushnow(rc,t[p].lazy);
- t[p].lazy=0;
- }
- }
- void build(ll p,ll l,ll r)
- {
- t[p].l=l;t[p].r=r;
- if(l==r)
- {
- t[p].minx=dis[l];
- t[p].lazy=0;return;
- }
- build(lc,l,mid);build(rc,mid+1,r);
- pushup(p);
- }
- void update(ll p,ll ql,ll qr,ll val)
- {
- if(ql<=t[p].l&&t[p].r<=qr)
- {
- pushnow(p,val);
- return ;
- }
- pushdown(p);
- if(ql<=mid)update(lc,ql,qr,val);
- if(qr>mid)update(rc,ql,qr,val);
- pushup(p);
- }
- ll query(ll p,ll ql,ll qr)
- {
- ll ans=INF;
- if(ql<=t[p].l&&t[p].r<=qr)
- return t[p].minx;
- pushdown(p);
- if(ql<=mid)
- ans=min(ans,query(lc,ql,qr));
- if(qr>mid)
- ans=min(ans,query(rc,ql,qr));
- pushup(p);
- return ans;
- }
- inline void add(ll u,ll v,ll w)
- {
- e[++cnt].nxt=first[u];first[u]=cnt;
- e[cnt].u=u;e[cnt].v=v;e[cnt].w=w;
- }
- void dfs(ll u,ll f)
- {
- for(int i=1;(1<<i)<=dep[u];i++)
- fa[u][i]=fa[fa[u][i-1]][i-1];
- for(int i=first[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==f)continue;
- dep[v]=dep[u]+1;
- fa[v][0]=u;
- dfs(v,u);
- }
- }
- ll lca(ll x,ll y)
- {
- if(dep[x]<dep[y])
- swap(x,y);
- ll t=dep[x]-dep[y];
- for(int i=0;(1<<i)<=t;i++)
- if(t&(1<<i))
- x=fa[x][i];
- if(x==y)
- return x;
- for(int i=19;i>=0;i--)
- if(fa[x][i]!=fa[y][i])
- {x=fa[x][i];y=fa[y][i];}
- return fa[x][0];
- }
- void getdfn(ll u,ll f,ll w)
- {
- st[u]=++idx;
- dis[st[u]]=w+rev[u];
- for(int i=first[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(v==f)continue;
- getdfn(v,u,w+e[i].w);
- }
- ed[u]=idx;
- }
- int main()
- {
- scanf("%lld%lld",&n,&q);
- for(int i=1;i<=(n-1)*2;i++)
- {
- ll u,v,w;
- scanf("%lld%lld%lld",&u,&v,&w);
- ux[i]=u;vx[i]=v;wx[i]=w;
- if(i<n){add(u,v,w);add(v,u,w);}
- else rev[u]=w;
- }
- getdfn(1,0,0);dfs(1,0);build(1,1,n);
- for(ll i=1;i<=q;i++)
- {
- ll x;
- scanf("%lld",&x);
- if(x==1)
- {
- ll k,w;
- scanf("%lld%lld",&k,&w);
- if(k>=n)
- {
- update(1,st[ux[k]],st[ux[k]],w-rev[ux[k]]);
- rev[ux[k]]=w;
- }
- else
- {
- update(1,st[vx[k]],ed[vx[k]],w-wx[k]);
- wx[k]=w;
- }
- }
- else
- {
- ll u,v;
- scanf("%lld%lld",&u,&v);
- if(lca(u,v)==u)
- {
- ll du=query(1,st[u],st[u])-rev[u];
- ll dv=query(1,st[v],st[v])-rev[v];
- printf("%lld\n",dv-du);
- }
- else
- {
- ll du=query(1,st[u],ed[u])-query(1,st[u],st[u])+rev[u];
- ll dv=query(1,st[v],st[v])-rev[v];
- printf("%lld\n",du+dv);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2720139.html