| ||||||||||
| 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