1 #include<cstdio>  2 #include<cstring>  3 #include<iostream>  4 #include<vector>  5 using namespace std;  6   7 inline int read(){  8     char ch;  9     int re=0; 10     bool flag=0; 11     while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘)); 12     ch==‘-‘?flag=1:re=ch-‘0‘; 13     while((ch=getchar())>=‘0‘&&ch<=‘9‘)  re=(re<<1)+(re<<3)+ch-‘0‘; 14     return flag?-re:re; 15 } 16  17 struct edge{ 18     int to,next; 19     edge(int to=0,int next=0): 20         to(to),next(next){} 21 }; 22  23 const int maxn=100001; 24  25 vector<edge> edges; 26 vector<edge> tree; 27 int head[maxn],tmp_head[maxn]; 28 int n,q,root,cnt; 29 int fat[maxn],dep[maxn],siz[maxn],son[maxn],top[maxn],id[maxn]; 30 //B[i]表示区间1...i变化量  31 int B[101]; 32 //C[i]表示区间1...i变化量的总和，有c[i]=b[i]*i  33 int C[101]; 34  35 inline void add_edge(int from,int to){ 36     edges.push_back(edge(to,head[from])); 37     head[from]=++cnt; 38     edges.push_back(edge(from,head[to])); 39     head[to]=++cnt; 40 } 41  42 inline void add_tree(int from,int to){ 43     tree.push_back(edge(to,tmp_head[from])); 44     tmp_head[from]=++cnt; 45 } 46  47 void init(){ 48     n=read();  q=read();  root=read(); 49     edges.push_back(edge(0,0)); 50     cnt=0; 51     for(int i=1;i<n;i++){ 52         int from=read(),to=read(); 53         add_edge(from,to); 54     } 55 } 56  57 void dfs_1(int x,int fa){ 58     fat[x]=fa; 59     dep[x]=dep[fa]+1; 60     siz[x]=1; 61     int maxx=0; 62     for(int ee=head[x];ee;ee=edges[ee].next) 63         if(edges[ee].to!=fa){ 64             add_tree(x,edges[ee].to); 65             dfs_1(edges[ee].to,x); 66             if(siz[edges[ee].to]>maxx){ 67                 maxx=siz[edges[ee].to]; 68                 son[x]=edges[ee].to; 69             } 70             siz[x]+=siz[edges[ee].to]; 71         } 72 } 73  74 void dfs_2(int x){ 75     if(son[x]){ 76         top[son[x]]=top[x]; 77         id[son[x]]=++cnt; 78         dfs_2(son[x]); 79     } 80     for(int ee=head[x];ee;ee=tree[ee].next) 81         if(tree[ee].to!=son[x]){ 82             top[tree[ee].to]=tree[ee].to; 83             id[tree[ee].to]=++cnt; 84             dfs_2(tree[ee].to); 85         } 86 } 87  88 void make(){ 89     cnt=0; 90     dep[0]=0; 91     tree.push_back(edge(0,0)); 92     dfs_1(root,0); 93     swap(head,tmp_head); 94     top[root]=root; 95     cnt=0; 96     dfs_2(root); 97 } 98  99 void ADD_B(int x, int c)100 {101      for (int i=x; i>0; i-=i&(-i)) B[i] += c;102 }103 104 void ADD_C(int x, int c)105 {106      for (int i=x; i<=n; i+=i&(-i)) C[i] += x * c;107 }108 109 int add(int left,int right,int c){110     ADD_B(right,c);  ADD_C(right,c);111     if(left-1){112         ADD_B(left-1,-c);113         ADD_C(left-1,-c);114     }115 }116 117 int SUM_B(int x)118 {119     int s = 0;120     for(int i=x;i<=n;i+=i&(-i)) s+=B[i];121     return s;122 }123 124 int SUM_C(int x)125 {126     int s=0;127     for (int i=x;i;i-=i&(-i)) s+=C[i];128     return s;129 }130 131 int SUM(int x)132 {133     if (x) return SUM_B(x)*x+SUM_C(x-1);134     else return 0;135 }136 137 int sum(int left,int right){138     return SUM(right)-SUM(left-1);139 }140 141 void cha(int u,int v,int a){142     int f1=top[u],f2=top[v];143     while(f1!=f2){144         if(dep[f1]<dep[f2]){145             swap(f1,f2);146             swap(u,v);147         }148         add(id[f1],id[u],a);149         u=fat[f1];  f1=top[u];150     }151     if(u==v)  return;152     if(dep[u]<dep[v])  swap(u,v);153     add(id[son[v]],id[u],a);154 }155 156 int calc(int u,int v){157     int f1=top[u],f2=top[v];158     int len=0;159     while(f1!=f2){160         if(dep[f1]<dep[f2]){161             swap(f1,f2);162             swap(u,v);163         }164         len+=sum(id[f1],id[u]);165         u=fat[f1];  f1=top[u];166     }167     if(u==v)  return len;168     if(dep[u]<dep[v])  swap(u,v);169     len+=sum(id[son[v]],id[u]);170     return len;171 }172 173 void solve(){174     for(int i=0;i<q;i++){175         int op=read(),ss=read(),tt=read();176         if(op){177             int a=read();178             cha(ss,tt,a);179         }180         else{181             printf("%d\n",calc(ss,tt));182         }183     }184 }185 186 int main(){187     //freopen("temp.in","r",stdin);188     init();189     make();190     solve();191     return 0;192 }