数据结构（树链剖分，线段树）：SDOI 2016 游戏

4515: [Sdoi2016]游戏

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 351 Solved: 157
[Submit][Status][Discuss]

Description

Alice 和 Bob 在玩一个游戏。

游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。

有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，

若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。

他需要先从这条路径上选择一个点，再从那个点上选择一个数字。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

Input

第一行两个数字 n、m，表示树的点数和进行的操作数。

接下来 n−1 行，每行三个数字 u、v、w，表示树上有一条连接 u、v 的边，长度是 w。

接下来 m 行。每行第一个数字是 1 或 2。

若第一个数是 1，表示 Alice 进行操作，接下来四个数字 s、t、a、b。

若第一个数是 2，表示 Bob 进行操作，接下来四个数字 s、t。

Output

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字

Sample Input

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

Sample Output

123456789123456789
6
-106

HINT

n≤100000，m≤100000，∣a∣≤10000,0<=w，|b|<=10^9

　　李超线段树？

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 const int maxn=100010;
  6 const long long INF=123456789123456789LL;
  7 int n,Q,cnt;
  8 int fir[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1];
  9 int dep[maxn],fa[maxn],sz[maxn],son[maxn];
 10 long long dis[maxn];
 11 void addedge(int a,int b,int v){
 12     nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;val[cnt]=v;
 13 }
 14 
 15 void DFS(int x){
 16     sz[x]=1;
 17     for(int i=fir[x];i;i=nxt[i])
 18         if(to[i]!=fa[x]){
 19             fa[to[i]]=x;
 20             dis[to[i]]=dis[x]+val[i];
 21             dep[to[i]]=dep[x]+1;
 22             DFS(to[i]);
 23             sz[x]+=sz[to[i]];
 24             if(sz[son[x]]<sz[to[i]])
 25                 son[x]=to[i];    
 26         }    
 27 }
 28 
 29 int top[maxn],ID[maxn],rID[maxn],tot;
 30 void DFS(int x,int tp){
 31     ID[x]=++tot;rID[tot]=x;top[x]=tp;
 32     if(son[x])DFS(son[x],tp);
 33     for(int i=fir[x];i;i=nxt[i])
 34         if(to[i]!=son[x]&&to[i]!=fa[x])
 35             DFS(to[i],to[i]);    
 36 }
 37 
 38 int Lca(int x,int y){
 39     while(top[x]!=top[y]){
 40         if(dep[top[x]]<dep[top[y]])swap(x,y);
 41         x=fa[top[x]];
 42     }
 43     return dep[x]<dep[y]?x:y;
 44 }
 45 
 46 struct Node{
 47     long long a,b;
 48     Node(long long a_=0,long long b_=INF){
 49         a=a_;b=b_;
 50     }
 51     long long Val(int x){
 52         return a*dis[rID[x]]+b;
 53     }
 54     int CmP(int l,int r,Node a){
 55         if(Val(l)<=a.Val(l)&&Val(r)<=a.Val(r))return 1;
 56         if(Val(l)>=a.Val(l)&&Val(r)>=a.Val(r))return -1;
 57         return 0;    
 58     }
 59 }F[maxn<<2];
 60 long long Min[maxn<<2];
 61 
 62 void Build(int x,int l,int r){
 63     Min[x]=INF;
 64     if(l==r)return;
 65     Build(x<<1,l,(l+r)>>1);
 66     Build(x<<1|1,((l+r)>>1)+1,r);
 67 }
 68 
 69 void Update(int x,int l,int r,int a,int b,Node p){
 70     int mid=(l+r)>>1;
 71     Min[x]=min(Min[x],min(p.Val(max(a,l)),p.Val(min(b,r))));
 72     if(l>=a&&r<=b){
 73         int tmp=p.CmP(l,r,F[x]);
 74         if(tmp==1)F[x]=p;
 75         if(tmp!=0)return;
 76         
 77         tmp=p.CmP(l,mid,F[x]);
 78         if(tmp!=1)Update(x<<1,l,mid,a,b,F[x]);
 79         
 80         tmp=p.CmP(mid+1,r,F[x]);
 81         if(tmp!=1)Update(x<<1|1,mid+1,r,a,b,F[x]);
 82     }
 83     if(l==r)return;
 84     if(mid>=a)Update(x<<1,l,mid,a,b,p);
 85     if(mid<b)Update(x<<1|1,mid+1,r,a,b,p);
 86 }
 87 
 88 void Modify(int x,int y,Node p){
 89     while(top[x]!=top[y]){
 90         Update(1,1,n,ID[top[x]],ID[x],p);
 91         x=fa[top[x]];
 92     }
 93     Update(1,1,n,ID[y],ID[x],p);
 94 }
 95 
 96 long long Query(int x,int l,int r,int a,int b){
 97     if(l>=a&&r<=b)return Min[x];
 98     int mid=(l+r)>>1;
 99     long long ret=min(F[x].Val(max(l,a)),F[x].Val(min(r,b)));
100     if(mid>=a)ret=min(ret,Query(x<<1,l,mid,a,b));
101     if(mid<b)ret=min(ret,Query(x<<1|1,mid+1,r,a,b));
102     return ret;
103 }
104 
105 long long Solve(int x,int y){
106     long long ret=INF;
107     while(top[x]!=top[y]){
108         if(dep[top[x]]<dep[top[y]])swap(x,y);
109         ret=min(ret,Query(1,1,n,ID[top[x]],ID[x]));
110         x=fa[top[x]];
111     }
112     if(dep[x]<dep[y])swap(x,y);
113     return min(ret,Query(1,1,n,ID[y],ID[x]));
114 }
115 
116 int main(){
117 #ifndef ONLINE_JUDGE
118     freopen("menci_game.in","r",stdin);
119     freopen("menci_game.out","w",stdout);
120 #endif
121     scanf("%d%d",&n,&Q);
122     for(int i=1,x,y,w;i<n;i++){
123         scanf("%d%d%d",&x,&y,&w);
124         addedge(x,y,w);addedge(y,x,w);
125     }
126     
127     DFS(1);
128     DFS(1,1);
129     Build(1,1,n);
130     
131     int type,s,t,lca;
132     long long a,b;
133     while(Q--){
134         scanf("%d",&type);
135         if(type==1){
136             scanf("%d%d%lld%lld",&s,&t,&a,&b);
137             lca=Lca(s,t);
138             Modify(s,lca,Node(-a,a*dis[s]+b));
139             Modify(t,lca,Node(a,a*(dis[s]-2*dis[lca])+b));
140         }
141         else{
142             scanf("%d%d",&s,&t);
143             printf("%lld
",Solve(s,t));
144         }
145     }
146     return 0;
147 }

尽最大的努力，做最好的自己！