谭松松的旅游计划

7 61 2 51 3 43 7 72 4 42 5 35 6 21 24 76 33 25 47 6

520149721 

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #define ll long long 8 const int MAXN=200005; 9 using namespace std;10 11 int N,M;12 int pa[30][MAXN],depth[MAXN],vis[MAXN];13 ll cost[30][MAXN];//注意long long 14 vector<int> G[MAXN],c[MAXN];15 16 void dfs(int x,int pre,int d){17     vis[x]=1;18     depth[x]=d;19     pa[0][x]=pre;20     for(int i=0;i<G[x].size();i++){21         int to=G[x][i];22         if(!vis[to]){23             cost[0][to]=c[x][i];24             dfs(to,x,d+1);25         }26     }27 }28 29 void init_lca(){30     memset(pa,-1,sizeof(pa));31     32     dfs(1,-1,0);33     for(int k=0;k<=25;k++){34         for(int i=1;i<=N;i++){35             if(pa[k][i]>0){36                 pa[k+1][i]=pa[k][ pa[k][i] ];37                 cost[k+1][i]=cost[k][i]+cost[k][ pa[k][i] ];38 //                cout<<cost[k+1][i]<<endl;39             }40         }41     }42 }43 44 ll lca(int u,int v){//long long45     ll sum=0;46     if(depth[u]>depth[v]) swap(u,v);47 //    cout<<u<<v<<endl;48     for(int k=0;k<25;k++){49         if((depth[v]-depth[u])>>k&1){50             sum+=cost[k][v];51             v=pa[k][v];//这两行不能换..... 52 //            cout<<cost[k][u]<<endl;53         }54     }55     56     if(u==v) return sum;57     for(int k=25;k>=0;k--){58         if(pa[k][u]!=pa[k][v]){59             sum+=(cost[k][u]+cost[k][v]);60             u=pa[k][u];61             v=pa[k][v];62         }63     }64     sum+=(cost[0][v]+cost[0][u]);65     return sum;66 }67 68 int main(){69 //    freopen("01.in","r",stdin);70     scanf("%d%d",&N,&M);71     for(int i=1;i<N;i++){72         int x,y,cc;73         scanf("%d%d%d",&x,&y,&cc);74         G[x].push_back(y);75         G[y].push_back(x);76         c[x].push_back(cc);77         c[y].push_back(cc);78     }79     init_lca();80     while(M--){81         int a,b;82         scanf("%d%d",&a,&b);83         printf("%lld\n",lca(a,b));//此处用cout会T!!! 84     }85     return 0;86 }

Line50 和Line51换了会爆炸

然后83用cout会爆炸，直接T掉

 

输出1万次就得用printf

cout也就比printf慢几千倍吧~