Time limit 433 ms //spoj的时限都那么奇怪

Memory limit 1572864 kB //1.5个G，疯了

Code length Limit 15000 B

OS Linux

Language limit All except: ERL JS-RHINO NODEJS PERL6 VB.NET

Source Special thanks to Ivan Krasilnikov for his alternative solution

Author Thanh-Vy Hua

吐槽

期中考第二个能A的题，结果写了半个小时，调了一个半小时……纪念一下第二道被多组Case读入害死的题目……这题是把下一个case的前两个数读进来了，是这次的case没读完就进入下一个case了，这才过了两个星期啊……下次测这种样例就该把样例多复制几遍……

顺便吐槽，这是啥数据啊……一步一步地向上暴力跳都能A，亏我还跳重链……而且case之间加空行这个要求它不会判，加不加空行都是AC

解题思路

我一看见这题就没多想，直接上树链剖分，结果写完反应过来杀鸡用牛刀，这题dfs预处理一遍，倍增跳树并统计结果是更优的办法，代码可以短不少。

树链剖分处理\(KTH\)操作是利用了一个性质：一条重链上的节点新id，从上到下是连续的，所以跳链的时候如果发现跳过了目标\(k\)，那么就直接使用这条重链两端的新\(id\)计算出目标\(k\)的\(id\)，然后转换成原来的的编号即可。另外，由于这题路径有了方向，所以跳链的时候不能像平时那样std::swap(u,v)，而是要判断应该跳u还是跳v，然后分情况写。

源代码

#include
    
     #include
     
      #include
      
       int T;int n;struct Edge{    int nxt,to,w;}e[200010];int head[100010],cnt;void add(int u,int v,int w){    e[cnt]={head[u],v,w};    head[u]=cnt++;    e[cnt]={head[v],u,w};    head[v]=cnt++;}struct Tree{    int fa,dep,w,sz,wson;    int top,id;}t[100010];void dfs1(int fa,int u,int w){    t[u].fa=fa;    t[u].dep=t[fa].dep+1;    t[u].w=w;    t[u].sz=1;    int maxn=0;    for(int i=head[u];i;i=e[i].nxt)    {        int v=e[i].to;        if(v==fa) continue;        dfs1(u,v,e[i].w);        int temp=t[v].sz;        t[u].sz+=temp;        if(temp>maxn)        {            maxn=temp;            t[u].wson=v;        }    }}int id=1;int mp[100010];//用新id查询老idlong long a[100010];void dfs2(int u,int top){    t[u].top=top;    t[u].id=id;    a[id]=t[u].w;    mp[id]=u;    id++;    if(t[u].sz==1) return;    dfs2(t[u].wson,top);    for(int i=head[u];i;i=e[i].nxt)    {        int v=e[i].to;        if(v==t[u].fa||v==t[u].wson) continue;        dfs2(v,v);    }}long long sum[400010];//线段树维护区间和void build(int x,int l,int r){    if(l==r)    {        sum[x]=a[l];        return;    }    int mid=l+r>>1;    build(x<<1,l,mid);    build(x<<1|1,mid+1,r);    sum[x]=sum[x<<1]+sum[x<<1|1];}long long quesum(int x,int l,int r,int ql,int qr){    if(qr
       
        >1;    long long ans=0;    if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);    if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);    return ans;}long long dist(int u,int v){    long long ans=0;    while(t[u].top!=t[v].top)    {        if(t[t[u].top].dep
        
         t[v].id) std::swap(u,v);    ans+=quesum(1,1,n,t[u].id+1,t[v].id);    return ans;}int kth(int ss,int tt,int k)//要区分起点和终点{    int num=0;    int u=ss,v=tt;//先跳一遍找到总的点数    while(t[u].top!=t[v].top)    {        if(t[t[u].top].dep
         
          t[v].id) std::swap(u,v); num+=t[v].id-t[u].id+1; while(t[ss].top!=t[tt].top)//跳链找答案 { if(t[t[ss].top].dep