树链剖分模板

边权

线段树

  1 const int MAXN=10005;
  2 struct Edge
  3 {
  4     int to, next;
  5 }edge[MAXN<<1];
  6 int head[MAXN], tot;
  7 int top[MAXN];
  8 int fa[MAXN];
  9 int deep[MAXN];
 10 int num[MAXN];
 11 int p[MAXN];
 12 int fp[MAXN];
 13 int son[MAXN];
 14 int pos;
 15 void init()
 16 {
 17     tot=0;
 18     memset(head, -1, sizeof(head));
 19     pos=0;
 20     memset(son, -1, sizeof(son));
 21 }
 22 void addedge(int u, int v)
 23 {
 24     edge[tot].to=v;
 25     edge[tot].next=head[u];
 26     head[u]=tot++;
 27 }
 28 void dfs1(int u, int pre, int d)
 29 {
 30     deep[u]=d;
 31     fa[u]=pre;
 32     num[u]=1;
 33     for(int i=head[u];i!=-1;i=edge[i].next)
 34     {
 35         int v=edge[i].to;
 36         if(v!=pre)
 37         {
 38             dfs1(v, u, d+1);
 39             num[u]+=num[v];
 40             if(son[u]==-1 || num[v]>num[son[u]])
 41                 son[u]=v;
 42         }
 43     }
 44 }
 45 void getpos(int u, int sp)
 46 {
 47     top[u]=sp;
 48     p[u]=pos++;
 49     fp[p[u]]=u;
 50     if(son[u]==-1)
 51         return ;
 52     getpos(son[u], sp);
 53     for(int i=head[u];i!=-1;i=edge[i].next)
 54     {
 55         int v=edge[i].to;
 56         if(v!=son[u] && v!=fa[u])
 57             getpos(v,  v);
 58     }
 59 }
 60 
 61 struct node
 62 {
 63     int l, r;
 64     int Max;
 65 }seg[MAXN*3];
 66 void build(int i, int l, int r)
 67 {
 68     seg[i].l=l;
 69     seg[i].r=r;
 70     seg[i].Max=0;
 71     if(l==r)
 72         return ;
 73     int mid=(l+r)>>1;
 74     build(i<<1, l, mid);
 75     build((i<<1)|1, mid+1, r);
 76 }
 77 void pushup(int i)
 78 {
 79     seg[i].Max=max(seg[i<<1].Max, seg[(i<<1)|1].Max);
 80 }
 81 void update(int i, int k, int val)
 82 {
 83     if(seg[i].l==k && seg[i].r==k)
 84     {
 85         seg[i].Max=val;
 86         return ;
 87     }
 88     int mid=(seg[i].l+seg[i].r)>>1;
 89     if(k<=mid)
 90         update(i<<1, k, val);
 91     else
 92         update(i<<1|1, k, val);
 93     pushup(i);
 94 }
 95 int query(int i, int l, int r)
 96 {
 97     if(seg[i].l==l && seg[i].r==r)
 98         return seg[i].Max;
 99     int mid=(seg[i].l+seg[i].r)>>1;
100     if(r<=mid)
101         return query(i<<1, l, r);
102     else if(l>mid)
103         return query((i<<1)|1, l, r);
104     else
105         return max(query(i<<1, l, mid), query((i<<1)|1, mid+1, r));
106 }
107 int find(int u, int v)
108 {
109     int f1=top[u], f2=top[v];
110     int tmp=0;
111     while(f1!=f2)
112     {
113         if(deep[f1]<deep[f2])
114         {
115             swap(f1, f2);
116             swap(u, v);
117         }
118         tmp=max(tmp, query(1, p[f1], p[u]));
119         u=fa[f1];
120         f1=top[u];
121     }
122     if(u==v)
123         return tmp;
124     if(deep[u]>deep[v])
125         swap(u, v);
126     return max(tmp, query(1, p[son[u]], p[v]));
127 }
128 
129 int e[MAXN][3];
130 int main()
131 {
132     int T;
133     scanf("%d", &T);
134     while(T--)
135     {
136         init();
137         int n;
138         scanf("%d", &n);
139         for(int i=0;i<n-1;i++)
140         {
141             scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
142             addedge(e[i][0], e[i][1]);
143             addedge(e[i][1], e[i][0]);
144         }
145         dfs1(1, 0, 0);
146         getpos(1,1);
147         build(1, 0, pos-1);
148         for(int i=0;i<n-1;i++)
149         {
150             if(deep[e[i][0]]>deep[e[i][1]])
151                 swap(e[i][0], e[i][1]);
152             update(1, p[e[i][1]], e[i][2]);
153         }
154         char op[10];
155         while(~scanf("%s", op))
156         {
157             if(op[0]=='D')
158                 break;
159             int u, v;
160             scanf("%d%d", &u, &v);
161             if(op[0]=='Q')
162                 printf("%d
", find(u, v));
163             else
164                 update(1, p[e[u-1][1]], v);
165         }
166     }
167     return 0;
168 }

SPOJ 375

点权

树状数组

  1 const int MAXN=50005;
  2 struct Edge
  3 {
  4     int to, next;
  5 }edge[MAXN<<1];
  6 int head[MAXN], tot;
  7 int top[MAXN];
  8 int fa[MAXN];
  9 int deep[MAXN];
 10 int num[MAXN];
 11 int p[MAXN];
 12 int fp[MAXN];
 13 int son[MAXN];
 14 int pos;
 15 void init()
 16 {
 17     tot=0;
 18     memset(head, -1, sizeof(head));
 19     pos=1;
 20     memset(son, -1, sizeof(son));
 21 }
 22 void addedge(int u, int v)
 23 {
 24     edge[tot].to=v;
 25     edge[tot].next=head[u];
 26     head[u]=tot++;
 27 }
 28 void dfs1(int u, int pre, int d)
 29 {
 30     deep[u]=d;
 31     fa[u]=pre;
 32     num[u]=1;
 33     for(int i=head[u];i!=-1;i=edge[i].next)
 34     {
 35         int v=edge[i].to;
 36         if(v!=pre)
 37         {
 38             dfs1(v, u, d+1);
 39             num[u]+=num[v];
 40             if(son[u]==-1 || num[v]>num[son[u]])
 41                 son[u]=v;
 42         }
 43     }
 44 }
 45 void getpos(int u, int sp)
 46 {
 47     top[u]=sp;
 48     p[u]=pos++;
 49     fp[p[u]]=u;
 50     if(son[u]==-1)
 51         return ;
 52     getpos(son[u], sp);
 53     for(int i=head[u];i!=-1;i=edge[i].next)
 54     {
 55         int v=edge[i].to;
 56         if(v!=son[u] && v!=fa[u])
 57             getpos(v,  v);
 58     }
 59 }
 60 
 61 int lowbit(int x)
 62 {
 63     return x & (-x);
 64 }
 65 int c[MAXN];
 66 int n;
 67 int sum(int i)
 68 {
 69     int s=0;
 70     while(i>0)
 71     {
 72         s+=c[i];
 73         i-=lowbit(i);
 74     }
 75     return s;
 76 }
 77 void add(int i, int val)
 78 {
 79     while(i<=n)
 80     {
 81         c[i]+=val;
 82         i+=lowbit(i);
 83     }
 84 }
 85 void change(int u, int v, int val)
 86 {
 87     int f1=top[u], f2=top[v];
 88     while(f1!=f2)
 89     {
 90         if(deep[f1]<deep[f2])
 91         {
 92             swap(f1, f2);
 93             swap(u, v);
 94         }
 95         add(p[f1], val);
 96         add(p[u]+1, -val);
 97         u=fa[f1];
 98         f1=top[u];
 99     }
100     if(deep[u]>deep[v])
101         swap(u, v);
102     add(p[u], val);
103     add(p[v]+1, -val);
104 }
105 
106 int a[MAXN];
107 int main()
108 {
109     int M, P;
110     while(~scanf("%d%d%d", &n, &M, &P))
111     {
112         init();
113         for(int i=1;i<=n;i++)
114             scanf("%d", &a[i]);
115         while(M--)
116         {
117             int u, v;
118             scanf("%d%d", &u, &v);
119             addedge(u, v);
120             addedge(v, u);
121         }
122         dfs1(1, 0, 0);
123         getpos(1,1);
124         memset(c, 0, sizeof(c));
125         for(int i=1;i<=n;i++)
126         {
127             add(p[i], a[i]);
128             add(p[i]+1, -a[i]);
129         }
130         while(P--)
131         {
132             char op[10];
133             scanf("%s", op);
134             if(op[0]=='Q')
135             {
136                 int x;
137                 scanf("%d", &x);
138                 printf("%d
", sum(p[x]));
139             }
140             else
141             {
142                 int x, y, z;
143                 scanf("%d%d%d", &x, &y, &z);
144                 if(op[0]=='D')
145                     z=-z;
146                 change(x, y, z);
147             }
148         }
149     }
150     return 0;
151 }

HDOJ 3966