fzu2082 过路费

fzu2082 过路费

​​ Problem Description 有n座城市，由n-1条路相连通，使得任意两座城市之间可达。每条路有过路费，要交过路费才能通过。每条路的过路费经常会更新，现问你，当前情况下，从城市a到城市b最少要花多少过路费。 Input 有多组样例，每组样例第一行输入两个正整数n,m(2 <= n<=50000，1<=m <= 50000),接下来n-1行，每行3个正整数a b c，(1 <= a,b <= n , a != b , 1 <= c <= 1000000000).数据保证给的路使得任意两座城市互相可达。接下来输入m行，表示m个操作，操作有两种：一. 0 a b，表示更新第a条路的过路费为b，1 <= a <= n-1 ； 二. 1 a b ， 表示询问a到b最少要花多少过路费。

Output 对于每个询问，输出一行，表示最少要花的过路费。 Sample Input 2 3 1 2 1 1 1 2 0 1 2 1 2 1 Sample Output 1 2 Source FOJ有奖月赛-2012年4月（校赛热身赛）

多组数据注意清0

#include#include#define N 55000inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int y,next,z;}data[N<<1];struct node1{ int left,right,l,r;long long sum;}tree[N<<2];inline void swap(int &x,int &y){ x^=y;y^=x;x^=y;}int size[N],a[N],h[N],son[N],w[N],id[N],num,dep[N],fa[N],tp[N],n,son1[N],root,m;void dfs1(int x){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (fa[x]==y) continue;a[y]=z;son1[i>>1]=y; dep[y]=dep[x]+1;fa[y]=x;dfs1(y),size[x]+=size[y]; if (size[y]>size[son[x]]) son[x]=y; }}void dfs2(int x,int top){ id[x]=++num;tp[x]=top;w[num]=a[x]; if (son[x]) dfs2(son[x],top); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x]==y||son[x]==y) continue; dfs2(y,y); }}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].sum=tree[l].sum+tree[r].sum;}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r) {tree[x].left=tree[x].right=0;tree[x].sum=w[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}void change(int x,int l,int v){ if (!x) return; if (tree[x].l==tree[x].r){tree[x].sum=v;return;} int mid=(tree[x].l+tree[x].r)>>1; if (l<=mid) change(tree[x].left,l,v); if (l>mid) change(tree[x].right,l,v); update(x);}long long query(int x,int l,int r){ if (!x) return 0; if (l<=tree[x].l&&r>=tree[x].r) return tree[x].sum; int mid=(tree[x].l+tree[x].r)>>1;long long tmp1=0; if (l<=mid) tmp1+=query(tree[x].left,l,r); if (r>mid) tmp1+=query(tree[x].right,l,r); return tmp1;}int main(){ freopen("fzu2082.in","r",stdin); while (~scanf("%d%d",&n,&m)){ num=1;memset(h,0,sizeof(h));memset(son,0,sizeof(son)); for (int i=1;iid[y]) swap(x,y);if (id[x]==id[y]) {printf("%lld\n",ans);continue;} ans+=query(root,id[x]+1,id[y]); printf("%lld\n",ans); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。