2016网站设计风格,宁德公司做网站,传奇做网站,做网站公司郑州题面 n点2n-2条有向边#xff0c;数据先给一颗1为根的生成树边集#xff0c;边目录按两部分给出 1、 开始的 n-1 条边描述了一颗以 1 号点为根的生成树#xff0c;即每个点都可以由 1 号点 到达。 2、 接下来的 N-1 条边#xff0c;一定是从 i 到 1#xff08;2iN…题面 n点2n-2条有向边数据先给一颗1为根的生成树边集边目录按两部分给出 1、 开始的 n-1 条边描述了一颗以 1 号点为根的生成树即每个点都可以由 1 号点 到达。 2、 接下来的 N-1 条边一定是从 i 到 12iN的有向边保证每个点都能到 然后给出除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 号点的边V1 接下来是 Q 行表示 Q 次修改与询问 【输出格式】 若干行每行回答一次询问 20%数据 没有修改 30%数据 2N,Q1000 (其中有 10%数据没有修改) 100%数据 2N,Q100 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序 #includebits/stdc.h
using namespace std;
#define N 200000
#define INF 0x7fffffff
#define ll long long
#define lc (p1)
#define rc (p1|1)
#define mid (t[p].lt[p].r1)
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].lazyval;t[p].minxval;
}inline void pushup(ll p)
{t[p].minxmin(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].lazy0;}
}void build(ll p,ll l,ll r)
{t[p].ll;t[p].rr;if(lr){t[p].minxdis[l];t[p].lazy0;return;}build(lc,l,mid);build(rc,mid1,r);pushup(p);
}void update(ll p,ll ql,ll qr,ll val)
{if(qlt[p].lt[p].rqr){pushnow(p,val);return ;}pushdown(p);if(qlmid)update(lc,ql,qr,val);if(qrmid)update(rc,ql,qr,val);pushup(p);
}ll query(ll p,ll ql,ll qr)
{ll ansINF;if(qlt[p].lt[p].rqr)return t[p].minx;pushdown(p);if(qlmid)ansmin(ans,query(lc,ql,qr));if(qrmid)ansmin(ans,query(rc,ql,qr));pushup(p);return ans;
}inline void add(ll u,ll v,ll w)
{e[cnt].nxtfirst[u];first[u]cnt;e[cnt].uu;e[cnt].vv;e[cnt].ww;
}void dfs(ll u,ll f)
{for(int i1;(1i)dep[u];i)fa[u][i]fa[fa[u][i-1]][i-1];for(int ifirst[u];i;ie[i].nxt){int ve[i].v;if(vf)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 tdep[x]-dep[y];for(int i0;(1i)t;i) if(t(1i))xfa[x][i];if(xy)return x;for(int i19;i0;i--)if(fa[x][i]!fa[y][i]){xfa[x][i];yfa[y][i];}return fa[x][0];
}void getdfn(ll u,ll f,ll w)
{st[u]idx;dis[st[u]]wrev[u];for(int ifirst[u];i;ie[i].nxt){int ve[i].v;if(vf)continue;getdfn(v,u,we[i].w);}ed[u]idx;
}int main()
{scanf(%lld%lld,n,q);for(int i1;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(in){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 i1;iq;i){ll x;scanf(%lld,x);if(x1){ll k,w;scanf(%lld%lld,k,w);if(kn){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 duquery(1,st[u],st[u])-rev[u];ll dvquery(1,st[v],st[v])-rev[v];printf(%lld\n,dv-du);}else{ll duquery(1,st[u],ed[u])-query(1,st[u],st[u])rev[u];ll dvquery(1,st[v],st[v])-rev[v];printf(%lld\n,dudv);} }} return 0;
} 转载于:https://www.cnblogs.com/NSD-email0820/p/9446553.html
