Main » 2013 November 21 » 树链剖分T2—SPOJ QTREE
4:17 PM 树链剖分T2—SPOJ QTREE |
这道题比起DISQUERY来就是用线段树上加一个修改了，其他部分一样，注意边的序号跟踪#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 20010 #define lc(x) (x<<1) #define rc(x) ((x<<1)+1) #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct node{int l,r,Max;}; int last[N],pre[N],e[N],W[N],idx[N]; int w[N],pos[N],siz[N],son[N],fa[N],dep[N],top[N],b[N]; int a[N];char OP[101]; int t1,t2,t3,n,q,len=0,size=0; void add(int x,int y,int z,int ID) {pre[++len]=last[x];last[x]=len;e[len]=y;W[len]=z;idx[len]=ID;} int swap(int &x,int &y){int t=x;x=y;y=t;} struct segtree { node tree[4*N]; void init(){memset(tree,0,sizeof(tree));} void update(int x){tree[x].Max=max(tree[lc(x)].Max,tree[rc(x)].Max);} void build(int x,int L,int R) { tree[x].l=L;tree[x].r=R;int mid=(L+R)>>1; if (L==R) {tree[x].Max=a[L];return;} build(lc(x),L,mid);build(rc(x),mid+1,R); update(x); } int query(int x,int L,int R) { if (tree[x].l==L&&tree[x].r==R) return tree[x].Max; int mid=(tree[x].l+tree[x].r)>>1; if (R<=mid) return query(lc(x),L,R); if (L>mid) return query(rc(x),L,R); return max(query(lc(x),L,mid),query(rc(x),mid+1,R)); } void modify(int x,int p,int ti) { if (tree[x].l==tree[x].r) {tree[x].Max=ti;return;} int mid=(tree[x].l+tree[x].r)>>1; if (p<=mid) modify(lc(x),p,ti); else modify(rc(x),p,ti); update(x); } }Tree; void DFS1(int x,int par,int Dep) { dep[x]=Dep;siz[x]=1;son[x]=0; for(int p=last[x];p;p=pre[p]) { int v=e[p],ID=idx[p]; if (par==v) continue; fa[v]=x;b[v]=W[p];pos[ID]=v; DFS1(v,x,Dep+1); if (son[x]==0||siz[v]>siz[son[x]]) son[x]=v; siz[x]+=siz[v]; } } void DFS2(int x,int Top) { w[x]=++size;top[x]=Top; a[size]=b[x]; if (son[x]!=0) DFS2(son[x],Top); for(int p=last[x];p;p=pre[p]) { int v=e[p]; if (v==fa[x]||v==son[x]) continue; DFS2(v,v); } } int getans(int va,int vb) { int f1=top[va],f2=top[vb],tmp=-1e9; while (f1!=f2) { if (dep[f1]<dep[f2]){swap(f1,f2);swap(va,vb);} tmp=max(tmp,Tree.query(1,w[f1],w[va])); va=fa[f1];f1=top[va]; } if (va==vb) return tmp; if (dep[va]>dep[vb]) swap(va,vb); return max(tmp,Tree.query(1,w[son[va]],w[vb])); } int Main() { memset(pre,0,sizeof(pre)); memset(last,0,sizeof(last)); memset(idx,0,sizeof(idx)); len=size=0;Tree.init(); scanf("%d",&n);int i; FOR(i,1,n-1) { scanf("%d%d%d",&t1,&t2,&t3); add(t1,t2,t3,i);add(t2,t1,t3,i); } DFS1(1,-1,1); DFS2(1,1); Tree.build(1,1,n); scanf("%s",OP); while (strcmp(OP,"DONE")!=0) { scanf("%d%d",&t1,&t2); if (strcmp(OP,"CHANGE")==0) { Tree.modify(1,w[pos[t1]],t2); }else { int ans=getans(t1,t2); printf("%d\n",ans); } scanf("%s",OP); } } int main() { int T; scanf("%d",&T); while (T--) Main(); } |
|
|
| Total comments: 0 | |