Archive

Archive for July, 2010

Poj 3277

July 29, 2010 Leave a comment

一开始以为这道题不需要传递参数,后来发现我错了..比如,先插入线段12 40 11,再插入13 40 13,若不传递参数,那么12~13这一段就会被无视

范围很大,要离散化;注意结果可能超int;区间划分时要注意

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 100001 #define MAXP 200001 #define MAXT 400001 struct segment{     int x,y,h; } seg[MAXN]; struct Point{     int x,id1,id2; } point[MAXP]; int N,pnum,tot; long long area[MAXT],height[MAXT],change[MAXP]; int cmp(const void *a, const void *b){     segment *x=(segment*)a, *y=(segment*)b;     return x->h-y->h; } int cmp1(const void *a, const void *b){     Point *x=(Point*)a, *y=(Point*)b;     return x->x-y->x; } void add(int p, int l, int r, int x, int y, int h){     if(l==x&&r==y||r-l<=1){         height[p]=h;         area[p]=(change[y]-change[x])*h;         return;     }     int m=l+r>>1;     if(height[p]){         height[p*2]=height[p*2+1]=height[p];         area[p*2]=(change[m]-change[l])*height[p];         area[p*2+1]=(change[r]-change[m])*height[p];     }     height[p]=0;     if(y<=m){         add(p*2,l,m,x,y,h);     }else if(x>=m){         add(p*2+1,m,r,x,y,h);     }else{         add(p*2,l,m,x,m,h);         add(p*2+1,m,r,m,y,h);     }     area[p]=area[p*2]+area[p*2+1]; } int main(){     scanf("%d\n",&N);     for(int i=1;i<=N;++i){         scanf("%d %d %d\n",&seg[i].x,&seg[i].y,&seg[i].h);         point[++pnum].x=seg[i].x;         point[pnum].id1=i;         point[pnum].id2=1;         point[++pnum].x=seg[i].y;         point[pnum].id1=i;         point[pnum].id2=2;     }     qsort(point+1,pnum,sizeof(point[0]),cmp1);     for(int i=1;i<=pnum;++i){         if(point[i].x!=point[i-1].x){             ++tot;             change[tot]=point[i].x;         }         if(point[i].id2==1){             seg[point[i].id1].x=tot;         }else{             seg[point[i].id1].y=tot;         }     }     qsort(seg+1,N,sizeof(seg[0]),cmp);     for(int i=1;i<=N;++i){         add(1,1,tot,seg[i].x,seg[i].y,seg[i].h);     }     printf("%lld\n",area[1]);     return 0; }
Advertisements
Categories: OI Tags: , , , ,

NOI 2008 志愿者招募

July 28, 2010 Leave a comment

这题竟然在省赛第3天中出现,要是当时有多做点NOI原题就好了

以样例来分析,设X[i]为第i类志愿者的人数,那么可得到约束为

Day[1]=X[1]>=2

Day[2]=X[1]+X[2]>=3

Day[3]=X[2]+X[3]>=4

添加辅助变量Y,将其化为等式得

Day'[1]=X[1]-Y[1]=2

Day'[2]=X[1]+X[2]-Y[2]=3

Day'[3]=X[2]+X[3]-Y[3]=4

添加第0、第4个等式,相邻等式两两相减(下减上)得

P[1]=X[1]-Y[1]=2

P[2]=X[2]+Y[1]-Y[2]=1

P[3]=X[3]+Y[2]-X[1]-Y[3]=1

P[4]=Y[3]-X[2]-X[3]=-4

进一步转化等式得

2-X[1]+Y[1]=0

1-X[2]-Y[1]+Y[2]=0

1-X[3]-Y[2]+X[1]+Y[3]=0

-4-Y[3]+X[2]+X[3]=0

分析上面四个等式,每个X[i]、Y[i]一正一负恰出现一次,若以每个等式为网络流中的顶点,上式就是流量守恒的形式

现规定以正为入,负为出,则对于每个P[i]:

若右端常数为正,从源点向该等式连边,容量为常数值,费用为0

若右端常数为负,从该等式向汇点连边,容量为常数值绝对值,费用为0

对于每个X[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为C[i]

对于每个Y[i],从它的正系数项出现的等式向负系数项出现的等式连边,容量为无穷大,费用为0

求最小费用最大流即为答案

#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 20001 #define QMAX 20001 #define MAXE 100001 #define oo 0x77777777 struct Edge{     int v,w,p;     Edge *next,*pair; } *edge[MAXN],*fe[MAXN],mempool[MAXE]; int S,T,memnum,dis[MAXN],Que[MAXN],vis[MAXN], Closed,Open,Size,ft[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w, int p){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->p=p,x->next=edge[s],x->pair=y,edge[s]=x;     y->v=s,y->w=0,y->p=-p,y->next=edge[t],y->pair=x,edge[t]=y; } int spfa(){     memset(dis,0x77,sizeof(dis));     memset(vis,0,sizeof(vis));     memset(ft,0,sizeof(ft));     memset(fe,0,sizeof(fe));     Closed=0,Open=0,Size=1,Que[0]=S,vis[S]=1,dis[S]=0;     while(Size){         int now=Que[Closed];         vis[now]=0,--Size,Closed=(Closed+1)%QMAX;         for(Edge *tmp=edge[now];tmp;tmp=tmp->next){             if(tmp->w>0){                 if(dis[now]+tmp->p<dis[tmp->v]){                     dis[tmp->v]=dis[now]+tmp->p;                     ft[tmp->v]=now;                     fe[tmp->v]=tmp;                     if(!vis[tmp->v]){                         ++Size;                         vis[tmp->v]=1;                         if(!Size||dis[tmp->v]<dis[Que[Closed]]){                             Closed=(Closed-1+QMAX)%QMAX;                             Que[Closed]=tmp->v;                         }else{                             Open=(Open+1)%QMAX;                             Que[Open]=tmp->v;                         }                     }                 }             }         }     }     return dis[T]<oo; } void aug(){     int delta=oo;     for(int i=T;i!=S;i=ft[i]){         if(fe[i]->w<delta){             delta=fe[i]->w;         }     }     for(int i=T;i!=S;i=ft[i]){         fe[i]->w-=delta,fe[i]->pair->w+=delta,ans+=delta*fe[i]->p;     } } int main(){     int N,M,x,y=0,s,t,c;     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     scanf("%d%d",&N,&M);     S=0,T=N+2;     for(int i=1;i<=N;++i){         scanf("%d",&x);         t=x-y;         if(t>0){             add(S,i,t,0);         }else{             add(i,T,-t,0);         }         y=x;         add(i+1,i,oo,0);     }     add(N+1,T,x,0);     for(int i=1;i<=M;++i){         scanf("%d%d%d",&s,&t,&c);         add(s,min(N+1,t+1),oo,c);     }     while(spfa())         aug();     printf("%d\n",ans);     return 0; }
Categories: OI Tags: , , , ,

NOI 2006 最大获利

July 28, 2010 Leave a comment

最大权闭合图。可参考胡伯涛的论文。该题的标准解法是贪心初始流+最大流。但用SAP+GAP+当前弧优化可以秒过。

早就听说当前弧优化,但是一加到自己代码上就错。这次终于找到原因了,因为以前把更新距离标号的一部分操作挪到寻找可行弧时完成,但这样一来就会出现问题。把操作独立出来之后问题就解决了。

#include<stdio.h> #include<string.h> #define MAXN 70001 #define MAXE 400001 #define oo 0x77777777 struct Edge{     int v,w;     Edge *next,*pair; } *edge[MAXN],mempool[MAXE],*cur[MAXN]; int S,T,counter[MAXN],layer[MAXN],minf,found,ans,memnum; inline int min(int a, int b){     return a<b?a:b; } void add(int s, int t, int w){     Edge *x=&mempool[memnum++],*y=&mempool[memnum++];     x->v=t,x->w=w,x->pair=y,x->next=edge[s],edge[s]=x;     y->v=s,y->w=0,y->pair=x,y->next=edge[t],edge[t]=y; } void aug(int now){     if(now==T){         found=1;         ans+=minf;         return;     }     Edge *i;     int tmp=minf;     for(i=cur[now];i;i=i->next){         if(i->w>0){             if(layer[now]==layer[i->v]+1){                 cur[now]=i;                 minf=min(minf,i->w);                 aug(i->v);                 if(layer[S]>T) return;                 if(found) break;                 minf=tmp;             }         }     }     if(!found){         int minl=T;         for(i=cur[now]=edge[now];i;i=i->next) if(i->w>0) minl=min(minl,layer[i->v]);         if(!(--counter[layer[now]])) layer[S]=T+1;         ++counter[layer[now]=minl+1];     }else{         i->w-=minf;         i->pair->w+=minf;     } } void sap(){     memset(counter,0,sizeof(counter));     memset(layer,0,sizeof(layer));     counter[0]=T+1;     memcpy(cur,edge,sizeof(edge));     while(layer[S]<=T){         found=0;         minf=oo;         aug(S);     } } int main(){     freopen("1.in","r",stdin);     freopen("1.out","w",stdout);     int sum=0,a,b,c,x,N,M;     scanf("%d %d\n",&N,&M);     S=0,T=N+M+1;     for(int i=1;i<=N;++i){         scanf("%d",&x);         add(i,T,x);     }     for(int i=1;i<=M;++i){         scanf("%d %d %d\n",&a,&b,&c);         add(i+N,a,oo);         add(i+N,b,oo);         add(S,i+N,c);         sum+=c;     }     sap();     printf("%d\n",sum-ans);     return 0; }
Categories: OI Tags: , , , ,

poj 1180

July 28, 2010 Leave a comment

可参见黑书P152
设F(i)表示前i个任务的代价以及之后任务的等待代价之和的最小值,则
F(i)=Min{F(j)+W[j+1,i]}
其中W[j+1,i]=(S+SumT(j+1,i))*SumF(j+1,n)
进一步可证明该方程满足决策单调性,因此可优化到O(nlogn)
此外本题有O(n)算法,详见黑书

#include<stdio.h> #include<string.h> #define MAXN 10001 #define oo 0x77777777 struct Stack{     int s,t,id; } stack[MAXN]; int N,S,sumt[MAXN],sumf[MAXN],f[MAXN],head,K; inline int min(int a, int b){     return a<b?a:b; } inline int getw(int i, int j){     return (S+sumt[j]-sumt[i])*(sumf[N]-sumf[i]); } inline int getf(int j, int i){     return f[j]+getw(j,i); } void update(int now){     while(head&&now<stack[head].s&&getf(now,stack[head].s)<getf(stack[head].id,stack[head].s)){         stack[head-1].t=stack[head].t;         --head;     }     int l=stack[head].s,r=stack[head].t,m;     while(l<=r){         m=l+r>>1;         if(getf(now,m)<getf(stack[head].id,m))             r=m-1;         else             l=m+1;     }     while(l<=stack[head].t&&getf(now,l)>getf(stack[head].id,l)) ++l;     stack[head].t=l-1;     if(stack[head].t<stack[head].s) --head;     if(l>N) return;     stack[++head].s=l;     stack[head].t=N;     stack[head].id=now; } int main(){     scanf("%d\n%d\n",&N,&S);     for(int i=1;i<=N;++i){         scanf("%d %d",&sumt[i],&sumf[i]);         sumt[i]+=sumt[i-1],sumf[i]+=sumf[i-1];     }     stack[head=1].s=1,stack[K=1].t=N;     for(int i=1;i<=N;++i){         if(i>stack[K].t)             ++K;         f[i]=getf(stack[K].id,i);         update(i);     }     printf("%d\n",f[N]);     return 0; }

网络流题目集锦

July 28, 2010 Leave a comment

转自http://hi.baidu.com/daizhy_acm/blog/item/c3e63252763ae66984352480.html

最大流
POJ 1273 Drainage Ditches
POJ 1274 The Perfect Stall (二分图匹配)
POJ 1698 Alice’s Chance
POJ 1459 Power Network
POJ 2112 Optimal Milking (二分)
POJ 2455 Secret Milking Machine (二分)
POJ 3189 Steady Cow Assignment (枚举)
POJ 1637 Sightseeing tour (混合图欧拉回路)
POJ 3498 March of the Penguins (枚举汇点)
POJ 1087 A Plug for UNIX
POJ 1149 Pigs (构图题)
ZOJ 2760 How Many Shortest Path (边不相交最短路的条数)
POJ 2391 Ombrophobic Bovines (必须拆点,否则有BUG)
WHU 1124 Football Coach (构图题)
SGU 326 Perspective (构图题,类似于 WHU 1124)
UVa 563 Crimewave
UVa 820 Internet Bandwidth
POJ 3281 Dining (构图题)
POJ 3436 ACM Computer Factory
POJ 2289 Jamie’s Contact Groups (二分)
SGU 438 The Glorious Karlutka River =) (按时间拆点)
SGU 242 Student’s Morning (输出一组解)
SGU 185 Two shortest (Dijkstra 预处理,两次增广,必须用邻接阵实现,否则 MLE)
HOJ 2816 Power Line
POJ 2699 The Maximum Number of Strong Kings (枚举+构图)
ZOJ 2332 Gems
JOJ 2453 Candy (构图题)
SOJ3312 Stockholm Knights
SOJ3353 Total Flow
SOJ2414 Leapin’ Lizards ­
最小割
SOJ3106 Dual Core CPU
SOJ3109 Space flight
SOJ3107 Select
SOJ3185 Black and white
SOJ3254 Rain and Fgj
SOJ3134 windy和水星 — 水星交通
HOJ 2634 How to earn more
ZOJ 2071 Technology Trader (找割边)
HNU 10940 Coconuts
ZOJ 2532 Internship (找关键割边)
POJ 1815 Friendship (字典序最小的点割集)
POJ 3204 Ikki’s Story I – Road Reconstruction (找关键割边)
POJ 3308 Paratroopers
POJ 3084 Panic Room
POJ 3469 Dual Core CPU
ZOJ 2587 Unique Attack (最小割的唯一性判定)
POJ 2125 Destroying The Graph (找割边)
ZOJ 2539 Energy Minimization
TJU 2944 Mussy Paper (最大权闭合子图)
POJ 1966 Cable TV Network (无向图点连通度)
HDU 1565 方格取数(1) (最大点权独立集)
HDU 1569 方格取数(2) (最大点权独立集)
POJ 2987 Firing (最大权闭合子图)
SPOJ 839 Optimal Marks (将异或操作转化为对每一位求最小割)
HOJ 2811 Earthquake Damage (最小点割集)
2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 预处理 )(http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322)
ZOJ 2676 Network Wars (参数搜索)
POJ 3155 Hard Life (参数搜索)
ZOJ 3241 Being a Hero

有上下界
ZOJ 2314 Reactor Cooling (无源汇可行流)
POJ 2396 Budget (有源汇可行流)
SGU 176 Flow Construction (有源汇最小流)
ZOJ 3229 Shoot the Bullet (有源汇最大流)
HDU 3157 Crazy Circuits (有源汇最小流)

最小费用流
HOJ 2715 Matrix3
HOJ 2739 The Chinese Postman Problem
POJ 2175 Evacuation Plan (消一次负圈)
POJ 3422 Kaka’s Matrix Travels (与 Matrix3 类似)
POJ 2516 Minimum Cost (按物品种类多次建图)
POJ 2195 Going Home
BUAA 1032 Destroying a Painting
POJ 2400 Supervisor, Supervisee (输出所有最小权匹配)
POJ 3680 Intervals
HOJ 2543 Stone IV
POJ 2135 Farm Tour
BASHU2445 餐巾问题
———————————————onmylove原创

最大流题目:

TC:

Single Round Match 200 Round 1 – Division I, Level Three

Single Round Match 236 Round 1 – Division I, Level Three

Single Round Match 399 Round 1 – Division I, Level Three

同Hoj1024: http://acm.hust.edu.cn/thx/problem.php?id=1024

2003 TCO Semifinal Round 4 – Division I, Level Three

2004 TCCC Championship Round – Division I, Level Three

2005 TCO Sponsor Track Round 3 – Division I, Level One

混合图的欧拉回路

Poj1637: http://acm.pku.edu.cn/JudgeOnline/problem?id=1637

zju1992:http://acm.zju.edu.cn/show_problem.php?pid=1992

求增广边:

Poj3204:http://acm.pku.edu.cn/JudgeOnline/problem?id=3204

类似:Hoj1082: http://acm.hust.edu.cn/thx/problem.php?cid=1017&pid=6

项目选择问题:

Poj3469:http://acm.pku.edu.cn/JudgeOnline/problem?id=3469

Zoj2930:http://acm.zju.edu.cn/show_problem.php?pid=2930

求项目选择项目最多的方案。

建图:

Poj1149:http://acm.pku.edu.cn/JudgeOnline/problem?id=1149

Poj3436:http://acm.pku.edu.cn/JudgeOnline/problem?id=3436

Poj3281:http://acm.pku.edu.cn/JudgeOnline/problem?id=3281

连通度:

点连通度Poj1966: http://acm.pku.edu.cn/JudgeOnline/problem?id=1966

Uva563, http://icpcres.ecs.baylor.edu/onlinejudge/

点不交的路径条数问题,需要拆点

最小割:

Poj2914:http://acm.pku.edu.cn/JudgeOnline/problem?id=2914

(stoer-Wagner)

基本题:

Poj3498:http://acm.pku.edu.cn/JudgeOnline/problem?id=3498

枚举:做n次最大流。

Poj1087:http://acm.pku.edu.cn/JudgeOnline/problem?id=1087

可以用最大流做,也可以用二分图匹配做。

Poj1273:http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

Poj1274:http://acm.pku.edu.cn/JudgeOnline/problem?id=1274

Poj1325: http://acm.pku.edu.cn/JudgeOnline/problem?id=1325

poj1459:http://acm.pku.edu.cn/JudgeOnline/problem?id=1459

Poj1797:http://acm.pku.edu.cn/JudgeOnline/problem?id=1797

Poj1815:http://acm.pku.edu.cn/JudgeOnline/problem?id=1815

poj2112:http://acm.pku.edu.cn/JudgeOnline/problem?id=2112

poj2239:http://acm.pku.edu.cn/JudgeOnline/problem?id=2239

poj2289: http://acm.pku.edu.cn/JudgeOnline/problem?id=2289

Poj2391:http://acm.pku.edu.cn/JudgeOnline/problem?id=2391

Poj2987:http://acm.pku.edu.cn/JudgeOnline/problem?id=2987

Poj3308:http://acm.pku.edu.cn/JudgeOnline/problem?id=3308

提示:最大权闭包,转化成最大流

Poj3155: http://acm.pku.edu.cn/JudgeOnline/problem?id=3155

SGU 176 http://acm.sgu.ru/problem.php?contest=0&problem=176

容量有上下界的网络流问题,有难度

Spoj660:http://www.spoj.pl/problems/QUEST4/

Spoj377:http://www.spoj.pl/problems/TAXI/

UVA

http://icpcres.ecs.baylor.edu/onlinejudge/

753,

820,

10122,

10330,

10511,

10735.

Categories: OI Tags:

poj 1144

July 28, 2010 Leave a comment

这题是求割点,参考《图论的算法与程序设计》中的算法即可

提供两个数据

1.in
21
17 4 18
1 11
7 5
13 1
3 1
14 5
15 20
9 12
6 8
16 14
18 8
8 4
20 18 10
2 3
12 5
5 9 20
19 20 9 11 2
11 3
4 15
10 3
21 3
0

1.out
6

2.in
63
30 11 33 52 9 25 47 28 59 29 32 18 7 35
51 15
19 47 25
32 27
9 46
7 59
13 53
35 17
6 2
63 21 35
52 40
4 58
27 61
43 54
49 16
11 44
25 57
60 54
21 35
23 41 50 11 2 25 3
59 1
33 41 15
53 57
22 62
57 19
34 7
44 46 39 57
48 29 3
47 48
18 29 25
10 38
62 25
56 23 8 62 46 30 6 44 43 60 29 45 26
3 6
40 12 31
38 45 22
8 11 43 13 49 18
14 49
55 10
5 49
28 3 14 61 20 24
54 35
29 5
46 31
45 44
17 54 19
39 61 58 2 26
61 37
1 52 58
12 62 31 56 43 28 61
36 12
58 44
26 29
31 3
50 52 6 28
16 10 51 25
20 54 47 13 29 4 6 44 52 32 53 39 57 3
42 48
0

2.out
7

#include<stdio.h> #include<string.h> #define MAXN 101 #define MAXE 20001 struct Edge{     int v;     Edge *next; } *edge[MAXN],mempool[MAXE]; int flag,n,snum,memnum,stack[MAXN],dfn[MAXN], low[MAXN],vis[MAXN],app[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int u, int v){     Edge *e=&mempool[memnum++];     e->v=v,e->next=edge[u],edge[u]=e; } int getn(){     int res=0;char ch;     for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())         res=res*10+ch-'0';     if(ch=='\n') flag=1;     return res; } void dfs(int now, int f){     stack[++snum]=now;     low[now]=dfn[now]=snum;     vis[now]=1;     int c=0;     for(Edge *i=edge[now];i;i=i->next){         if(i->v!=f){             if(vis[i->v]){                 low[now]=min(low[now],dfn[i->v]);             }else{                 ++c;                 dfs(i->v,now);                 low[now]=min(low[now],low[i->v]);                 if(f&&low[i->v]>=dfn[now]&&!app[now]){                     ++ans;                     app[now]=1;                 }             }         }     }     if(!f&&c>1&&!app[now]) ++ans; } void init(){     memnum=0;     ans=0;     snum=0;     memset(edge,0,sizeof(edge));     memset(app,0,sizeof(app));     memset(vis,0,sizeof(vis));     memset(dfn,0,sizeof(dfn));     memset(low,0,sizeof(low)); } int main(){     int now,t;     while(scanf("%d\n",&n)!=EOF){         if(!n) break;         init();         while(now=getn()){             if(!now) break;             flag=0;             while(t=getn()){                 add(now,t);                 add(t,now);                 if(flag) break;             }         }         if(n<=2) printf("0\n");         else{             dfs(1,0);             printf("%d\n",ans);         }     }     return 0; }
Categories: OI Tags: , , ,

poj 2763

July 27, 2010 Leave a comment

这题要求两个操作:求树上两个顶点的距离,以及改变某条边的权值。

通过巧妙地利用DFS序列和树状数组,我们可以在O(lg n)时间内完成每个操作。

比如对于一个有8个顶点,且边集如下的树:

1 2

1 3

1 4

2 5

2 6

4 7

7 8

它的DFS序列为 1 2 5 6 3 4 7 8

对于某条树上的边,我们将边指向的子结点的权值加上边的权值,再将这棵子树之后的第一个结点的权值减去这条边的权值,那么就可以用一个树状数组维护每个结点到根结点的距离。

比如 连接1和2的这条边权值为3,我们在2上加3,在3上减3即可。这样修改边权也非常方便。

两个结点间距离:dis(a)+dis(b)-2*dis(LCA(Tree,a,b))

拿这题来复习树状数组,RMQ,LCA…

要注意几个情况

RE一般是数组没开够 开大点..

TLE可能是算法没优化好 实在不行试试用getchar输入加速

WA原因很多,要注意结点到自身的LCA

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 222222
struct Edge{
	int v,w;
	Edge *next;
} *edge[MAXN], mempool[MAXN];
int memnum, road[MAXN][3], dep[MAXN], vis[MAXN], tapp[MAXN],
stack[MAXN], app[MAXN], snum, tnum, n, q, cur, tree[MAXN],
son[MAXN], cnum[MAXN], st[MAXN][20];
inline int rmin(int a, int b){
	return dep[a]<dep[b]?a:b;
}
void add(int u, int v, int w){
	Edge *e=&mempool[memnum++];
	e->v=v,e->w=w,e->next=edge[u],edge[u]=e;
}
int getn(){
	char ch;
	int res=0;
	for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())
		res=res*10+ch-'0';
	return res;
}
void predfs(int now, int deep){
	dep[now]=deep;
	vis[now]=1;
	stack[++snum]=now;
	tree[++tnum]=now;
	tapp[now]=tnum;
	if(!app[now]) app[now]=snum;
	for(Edge *tmp=edge[now];tmp;tmp=tmp->next){
		if(!vis[tmp->v]){
			predfs(tmp->v,deep+1);
			stack[++snum]=now;
			son[now]+=son[tmp->v]+1;
		}
	}
}
void find(int i, int k){
	if(k==0){
		st[i][k]=stack[i];
		return;
	}
	if(!st[i][k-1]) find(i,k-1);
	if(!st[i+(1<<(k-1))][k-1]) find(i+(1<<(k-1)),k-1);
	st[i][k]=rmin(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
int rmq(int l, int r){
	int k=int(log(1.0*(r-l+1))/log(2.0)),kr=r-(1<<k)+1;
	if(!st[l][k]) find(l,k);
	if(!st[kr][k]) find(kr,k);
	return rmin(st[l][k], st[kr][k]);
}
int getsum(int x){
	int res=0;
	for(;x>0;x-=x&-x)
		res+=cnum[x];
	return res;
}
void add(int x, int d){
	for(;x<=n;x+=x&-x)
		cnum[x]+=d;
}
int lca(int a, int b){
	if(a==b) return a;
	int x=app[a], y=app[b];
	if(x<y) return rmq(x,y);
	else return rmq(y,x);
}
int dist(int now){
	return getsum(tapp[now]);
}
int ask(int a, int b){
	return dist(a)+dist(b)-2*dist(lca(a,b));
}
void change(int i, int w){
	int a=road[i][0], b=road[i][1];
	if(dep[a]>dep[b]){int tmp=a;a=b;b=tmp;}
	add(tapp[b], w-road[i][2]);
	add(tapp[b]+son[b]+1, road[i][2]-w);
	road[i][2]=w;
}
int main(){
	int u,a,b,w,c;
	scanf("%d %d %d\n",&n,&q,&cur);
	for(int i=1;i<n;++i){
		a=getn(), b=getn(), w=getn();
		add(a,b,w);
		add(b,a,w);
		road[i][0]=a;
		road[i][1]=b;
		road[i][2]=w;
	}
	predfs(1,0);
	for(int i=1;i<n;++i){
		w=road[i][2];
		road[i][2]=0;
		change(i,w);
	}
	for(int i=1;i<=q;++i){
		c=getn();
		if(!c){
			u=getn();
			printf("%d\n",ask(cur,u));
			cur=u;
		}else{
			a=getn(), b=getn();
			change(a,b);
		}
	}
	return 0;
}
Categories: OI Tags: , , , , ,