Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
为什么我写的光RE#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 100001; int dep[maxn],siz[maxn],son[maxn],top[maxn],id[maxn],fa[maxn],cnt,h[maxn],val[maxn],n,q,s,a,b,t,pos,num; int e[maxn][3]; struct edge{ int fr,to,next; }edges[maxn<<1]; struct segtree{ int l,r,val; }tr[maxn*6]; inline void init(){ cnt = 0; memset(h,-1,sizeof(h)); memset(dep,0,sizeof(dep)); memset(siz,0,sizeof(siz)); memset(fa,0,sizeof(fa)); memset(id,0,sizeof(id)); memset(edges,0,sizeof(edge)); memset(val,0,sizeof(val)); memset(e,0,sizeof(e)); memset(top,0,sizeof(top)); memset(tr,0,sizeof(tr)); num = 0; } inline void addedge(int u,int v){ edges[cnt].fr = u;edges[cnt].to = v;edges[cnt].next = h[u]; h[u] = cnt++; } void dfs1(int now,int father,int d){ dep[now] = d; fa[now] = father; siz[now] = 1; son[now] = 0; for(int i = h[now];i != -1;i = edges[i].next){ edge e1 = edges[i]; if(e1.to == father)continue; dfs1(e1.to,now,d+1); siz[now] += siz[e1.to]; if(siz[e1.to] > siz[son[now]]){ son[now] = e1.to; } } } void getpos(int now,int tp){ top[now] = tp; id[now] = ++num; if(son[now])getpos(son[now],tp); for(int i = h[now];i != -1;i = edges[i].next){ edge e1 = edges[i]; if(e1.to == son[now] || e1.to == fa[now])continue; getpos(e1.to,e1.to); } } void push_up(int v){ tr[v].val = tr[v<<1].val + tr[v<<1|1].val; } void build(int l,int r,int now){ tr[now].l = l; tr[now].r = r; if(l == r){ tr[now].val = val[l]; return; } int mid = (l + r) >> 1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); push_up(now); } void update(int now,int v,int val){ if(tr[now].l = tr[now].r){ tr[now].val = val; return; } int mid = (tr[now].l + tr[now].r) >> 1; if(v <= mid)update(now<<1,v,val); else update(now<<1|1,v,val); push_up(now); } int query(int x,int l,int r){ if (l <= tr[x].l && tr[x].r <= r){ return tr[x].val; } int mid = (tr[x].l + tr[x].r) >> 1; int ans = 0; if(l <= mid)ans += query(x<<1,l,r); if(r > mid)ans += query(x<<1|1,l,r); return ans; } int find(int u,int v){ int ans = 0; while(top[u] != top[v]){ if(dep[top[u]] < dep[top[v]])swap(u,v); ans += query(1,id[top[u]],id[u]); u = fa[top[u]]; } if(u == v)return ans; if(dep[u] > dep[v])swap(u,v); ans += query(1,id[son[u]],id[v]); return ans; } int main(){ while(scanf("%d%d%d",&n,&q,&s) != EOF){ pos = s; init(); for(int i = 1;i < n;++i){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]); addedge(e[i][1],e[i][0]); } dfs1(s,-1,1); getpos(s,s); for(int i = 1;i < n;++i){ if(dep[e[i][0]] < dep[e[i][1]])swap(e[i][0],e[i][1]); val[id[e[i][0]]] = e[i][2]; } build(1,n,1); for(int i = 1;i <= q;++i){ scanf("%d",&t); if(t == 0){ scanf("%d",&a); printf("%d\n",find(pos,a)); pos = a; } else if(t == 1){ scanf("%d%d",&a,&b); update(1,id[e[a][0]],b); } } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator