树链剖分——边上权值和

Queries On Tree

Problem code: TAQTREE

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

You are given a tree of N nodes numbered from 1 to N.
The i^th edge connecting node u_i and v_i has a weight of w_i.

Your target is to handle the queries of the following two types:

"1 i c" : Update the weight of i^th edge with the new weight c.
(1 represents the query type).

"2 u v" : Find the length of the path from node u to v. (2 represents the query type).

Input

The first line contains a single integer N.
Each of the next N - 1 lines contains three integers u v w, representing an edge
between u and v with the weight of w.
The next line contains a single integer Q representing the number of queries
Each of the next Q lines contains three integers representing a query as described above.

Output

For each query of type 2, output the answer in a single line.

Constraints

All test:

1 ≤ i < N
1 ≤ u, v ≤ N; u ≠ v
1 ≤ w, c ≤ 10⁴

40 points:

1 ≤ N, Q ≤ 10³

60 points:

1 ≤ N, Q ≤ 10⁵

Example

Input: 5 1 2 2 2 3 4 4 2 3 5 4 1 3 2 5 3 1 3 1 2 5 3  Output: 8 6

Explanation

The path from 5 to 3 is 5 -> 4 -> 2 -> 3. Initially this path has the length of 1 + 3 + 4 = 8.
After the weight of the edge connect 4 and 2 was changed to 1, the new length of the path is 1 + 1 + 4 = 6.

比较基础的树链剖分题，算边上的权值和，单边修改

  1 #include<bits/stdc++.h>
  2
  3 using namespace std;
  4 typedef long long ll;
  5
  6 #define N 223456
  7 struct node
  8 {
  9     int v,next;
10 }e[N<<2];
11 int head[N],tot,top[N],fa[N],deep[N],num[N];
12 int p[N],fp[N],son[N];
13 int pos;
14
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 add(int u,int v)
23 {
24     e[tot].v=v;
25     e[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=e[i].next)
34     {
35         int v=e[i].v;
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]]) son[u]=v;
41         }
42     }
43 }
44 void getpos(int u,int sp)
45 {
46     top[u]=sp;
47     p[u]=pos++;
48     fp[p[u]]=u;
49     if (son[u]==-1) return;
50     getpos(son[u],sp);
51     for (int i=head[u];i!=-1;i=e[i].next)
52     {
53         int v=e[i].v;
54         if (v!=son[u]&&v!=fa[u])
55             getpos(v,v);
56     }
57 }
58
59 struct nod
60 {
61     int l,r;
62     ll sum;
63 }tree[N<<4];
64
65 void build(int rt,int l,int r)
66 {
67     tree[rt].l=l;
68     tree[rt].r=r;
69     tree[rt].sum=0;
70     if (l==r) return;
71     int mid=(l+r)/2;
72     build(rt<<1,l,mid);
73     build(rt<<1|1,mid+1,r);
74 }
75
76 void pushup(int rt)
77 {
78     tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
79 }
80 void update(int rt,int k,int val)
81 {
82     if (tree[rt].l==k&&tree[rt].r==k)
83     {
84         tree[rt].sum=val;
85         return;
86     }
87     int mid=(tree[rt].l+tree[rt].r)/2;
88     if (k<=mid) update(rt<<1,k,val);
89     else update(rt<<1|1,k,val);
90     pushup(rt);
91 }
92
93 ll query(int rt,int l,int r)
94 {
95     if (tree[rt].l==l&&tree[rt].r==r) return tree[rt].sum;
96
97     int mid=(tree[rt].l+tree[rt].r)/2;
98     if (r<=mid) return query(rt<<1,l,r);
99     else if (l>mid) return query(rt<<1|1,l,r);
100     else return query(rt<<1,l,mid)+query(rt<<1|1,mid+1,r);
101 }
102
103 ll find(int u,int v)
104 {
105     int f1=top[u],f2=top[v];
106     ll tmp=0;
107     while (f1!=f2)
108     {
109         if (deep[f1]<deep[f2])
110         {
111             swap(f1,f2);
112             swap(u,v);
113         }
114         tmp+=query(1,p[f1],p[u]);
115         u=fa[f1];
116         f1=top[u];
117     }
118     if (u==v) return tmp;
119     if (deep[u]>deep[v]) swap(u,v);
120     return tmp+query(1,p[son[u]],p[v]);
121 }
122
123 int x[N],y[N],z[N];
124 int main()
125 {
126     int n;
127     scanf("%d",&n);
128     init();
129     for (int i=1;i<n;i++)
130     {
131         scanf("%d%d%d",&x[i],&y[i],&z[i]);
132         add(x[i],y[i]);
133         add(y[i],x[i]);
134     }
135     dfs1(1,0,0);
136     getpos(1,1);
137     build(1,0,pos-1);
138     for (int i=1;i<n;i++)
139     {
140         if (deep[x[i]]>deep[y[i]])
141             swap(x[i],y[i]);
142         update(1,p[y[i]],z[i]);
143     }
144     int Q;
145     scanf("%d",&Q);
146     while (Q--)
147     {
148         int ty,a,b;
149         scanf("%d%d%d",&ty,&a,&b);
150         if (ty==1) update(1,p[y[a]],b);
151         else printf("%lld ",find(a,b));
152     }
153
154     return 0;
155 }