感觉这道题挺不错的
一开始用LCA(Tarjan)做，对于每一对询问(u, v)，若LCA(u,v)==u，那么就满足条件，所需时间为:

timeFromRoot(v) - timeFromRoot(u)

只过前5个点，后5个超时

后来发现其实只要找u是否为v的祖先即可，改用一个数组存每个点的父亲节点，从v往根节点找，如果找到u，那么满足条件，所需时间就是搜索路径上的时间总和。但还是有3个点超时

然后发觉“搜索路径上的时间总和”可能会重复求多次，一气之下加了一个记忆化搜索，但最终还有一个点超时

走投无路后看题解，发现有时间戳这个好东西，用了之后速度提升极大，AC

下面说一下时间戳：
我们知道树的前序遍历与后序遍历，时间戳其实就是这两个东西演化而来。使用一个全局变量timeStamp，两个数组begin和end，分别记录到达一个节点时，与拓展完一个节点后，timeStamp的值。换句话说，begin数组存储树前序遍历的顺序，end数组存储树后序遍历的顺序。

这样遍历完整棵树后，就可以处理询问了。根据前序遍历与后序遍历的知识，我们知道，i 的父节点的前序遍历一定比 i 早；后序遍历一定比 i 晚。所以说 j 为 i 的祖先，当且仅当 j 比 i 前序遍历早、后序遍历晚。由于之前记录了前、后序遍历的先后，所以这个判断非常简单：

begin[j]<=begin[i] && end[j]>=end[i]
此时j为i的祖先

放代码：

void dfs(int root, long long time){
edge *p = tree[root];
timeFromRoot[root] = time;
begin[root] = timeStamp++;
while(p != NULL){
dfs(p->to, time + p->time);
p = p->next;
}
end[root] = timeStamp++;
}

请注意这段dfs中还附加了对距离的计算，一箭双雕嘛
另外，这题最好用链式存储。虽说有人投机取巧开了个 10000*15 的邻接矩阵也能过，但毕竟不是完美方法。

写LCA的都是什么心态？明明求出dfs序然后判断一下是否为ins[u]<=ins[v]&&ins[v]<-ous[u]$不就好了？O(1)可以干的事情非得上log?

#include<bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
#define MOD 998244353
using namespace std;
const int maxn=10010;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f*x;
}

struct edge{
    int to,pre;
    ll val;
}G[maxn];

int n,m,Len,cl,ans;
int head[maxn],ins[maxn],ous[maxn],fa[maxn];
ll tot;
ll s[maxn];

inline void addedge(int x,int y,ll z){G[++Len].to=y;G[Len].pre=head[x];G[Len].val=z;head[x]=Len;}
inline void dfs(int u){
    ins[u]=++cl;
    for (int i=head[u];i;i=G[i].pre)s[G[i].to]=s[u]+G[i].val,dfs(G[i].to);
    ous[u]=cl;
}

int main(){
    n=read();m=read();
    int x,y;ll z;
    for (int i=1;i<n;++i){
        x=read();y=read();scanf("%lld",&z);
        fa[y]=x;
        addedge(x,y,z);
    }
    for (int i=1;i<=n;++i)if (!fa[i])dfs(i);
    ans=tot=0;
    while (m--){
        x=read();y=read();
        if (ins[x]<=ins[y]&&ins[y]<=ous[x]){
            ++ans;tot+=s[y]-s[x];
        }
    }
    printf("%d\n%lld\n",ans,tot);
}

sum[i]记录i节点到根节点的时间，使用时间戳判断u是否为v的祖先（时间戳用法详见 wang_yanheng发表于2015-08-20 13:36），若是的话，s（数量）+1，ans（总时间）+sum[v]-sum[u]。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=10010;
vector<int> edge[N];
vector<long long> val[N];
int Begin[N],End[N],Sum[N],indeg[N];
int cnt1,cnt2,n,m;
long long s,ans;
void dfs(int r){
Begin[r]=++cnt1;
int j;
for (int i=0;i<edge[r].size();i++){
j=edge[r][i];
Sum[j]=Sum[r]+val[r][i];
dfs(j);
}
End[r]=++cnt2;
}
int main(){
scanf("%d%d",&n,&m);
memset(Begin,0,sizeof(Begin));
memset(End,0,sizeof(End));
memset(Sum,0,sizeof(Sum));
for (int i=1;i<=n;i++){
edge[i].clear();
val[i].clear();
}
int u,v,o;
for (int i=1;i<=n-1;i++){
scanf("%d%d%d",&u,&v,&o);
edge[u].push_back(v);
val[u].push_back(o);
indeg[v]++;
}
for (int i=1;i<=n;i++)
if (!indeg[i]){
cnt1=cnt2=0;dfs(i);
break;
}
ans=s=0;
for (int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if ((Begin[u]<=Begin[v])&&(End[u]>=End[v])){
s++;ans+=Sum[v]-Sum[u];
}
}
printf("%lld\n",s);
printf("%lld\n",ans);
}

虽然时间复杂度高，但是还是卡着时间过了，最慢的点939ms。
思路很简单，逆向存边，一个个找爹，找到为止。

#include <iostream>

using namespace std;

int n,m;
int fa[10001][2]={0};

int main()
{
    cin>>n>>m;
    int i,j,k,l;
    for(i=1;i<n;i++)
    {
        cin>>j>>k>>l;
        fa[k][0]=j;
        fa[k][1]=l;
    }
    fa[1][0]=0;
    fa[1][0]=0;
    int a,b;
    unsigned long long acc=0;
    unsigned long long len=0;
    unsigned long long ans;
    while(m>0)
    {
        m--;
        ans=0;
        cin>>a>>b;
        while(b!=a&&b!=0)
        {
            ans+=fa[b][1];
            b=fa[b][0];
        }
        if(b==a)
        {
            acc++;
            len+=ans;
        }
    }
    cout<<acc<<endl<<len<<endl;
    return 0;
}

tarjan硬做没毛病，这是道LCA模板题
其实是我太弱想不到正解。。。

#include<iostream>
#include<vector>
using namespace std;
vector<int> q[10010],p[10010],num[100010],lian[100010],sai[100010];
int u[100010],v[100010],wen[100010],ans[100010],f[100010],c[100010],shen[100010];

int find(int x)
{
    if(x!=f[x])
     return f[x]=find(f[x]);
    return f[x];
}

void dfs(int a,int b)
{
    int hao=num[a].size();
    for(int i=0;i<hao;i++)
    {
        wen[num[a][i]]++;
        if(wen[num[a][i]]==2)
        {
            ans[num[a][i]]=find(lian[a][i]);
        }
    }
    int d=q[a].size();
    for(int i=0;i<d;i++)
    {
        int ha=q[a][i];
        if(ha!=b)
        {
            c[ha]=c[a]+1;
            shen[ha]=shen[a]+p[a][i];
            dfs(ha,a);
        }
    }
    f[a]=find(b);
}

int main()
{
    int n,m,i,a,b,t,maxn=0;
    long long ha=0;
    cin>>n>>m;
    for(i=1;i<n;i++)
    {
        cin>>a>>b>>t;
        q[a].push_back(b);
        q[b].push_back(a);
        p[a].push_back(t);
        p[b].push_back(t);
    }
    for(i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        lian[u[i]].push_back(v[i]);
        lian[v[i]].push_back(u[i]);
        num[u[i]].push_back(i);
        num[v[i]].push_back(i);
    }
    for(i=1;i<=n;i++)
     f[i]=i;
    dfs(1,1);
    for(i=1;i<=m;i++)
    {
        if(ans[i]==u[i])
        {
            maxn++;
            ha+=shen[v[i]]-shen[u[i]];
        }
    }
    cout<<maxn<<endl<<ha;
    return 0;
}

有点意思。。。

第3個測試點
第1行是511 500
然而後面有512 499（請自行用Ctrl+F搜尋，一共出現了3次）
請在讀入時

x=((x<1)?1:x);
x=((x>n)?n:x);
y=((y<1)?1:y);
y=((y>n)?n:y);

完整AC代碼

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

long long n,m,cnt,ans;
long long R=1;
long long fa[10000+1];
long long e_x[10000+1];
long long e_y[10000+1];
long long e_d[10000+1];
long long dep[10000+1];
long long dis[10000+1];
long long vis[10000+1];
long long rec_f[10000+1];
vector<long long> rec_p;
vector<long long> rec_d;
vector<long long> st_rec_d_l;
vector<long long> st_rec_d_r;
vector<long long> st_rec_d_mid;
vector<long long> st_rec_d_min;
vector<long long> st_rec_d_min_p;
vector<vector<long long> > e;
vector<vector<long long> > d;
deque<long long> q;

void pr_q_1()
{
    q.clear();
    for (long long i=1;i<n;i++)
        q.push_back(i);
}

void pr_tree_1()
{
    e.clear();
    e.resize(n+1);
    d.clear();
    d.resize(n+1);
    memset(dep,0,sizeof(dep));
    dep[R]=0;
    memset(dis,0,sizeof(dis));
    dis[R]=0;
    memset(vis,0,sizeof(vis));
    vis[R]=1;
    memset(fa,0,sizeof(fa));
    for (pr_q_1();!q.empty();q.pop_front())
    {
        long long now=q.front();
        if (vis[e_x[now]]==1||vis[e_y[now]]==1)
        {
            if (vis[e_y[now]]==1)
                swap(e_x[now],e_y[now]);
            vis[e_y[now]]=1;
            dep[e_y[now]]=dep[e_x[now]]+1;
            dis[e_y[now]]=dis[e_x[now]]+e_d[now];
            fa[e_y[now]]=e_x[now];
            e[e_x[now]].push_back(e_y[now]);
            d[e_x[now]].push_back(e_d[now]);
        }
        else
            q.push_back(now);
    }
}

void update_rec_1(long long now)
{
    rec_p.push_back(now);
    rec_d.push_back(dep[now]);
    if (rec_f[now]==0)
        rec_f[now]=rec_p.size()-1;
}

void dfs_tree_2(long long now);

void dfs_tree_1(long long now)
{
    rec_p.clear();
    rec_p.resize(1,0);
    rec_d.clear();
    rec_d.resize(1,0);
    memset(rec_f,0,sizeof(rec_f));
    update_rec_1(now);
    dfs_tree_2(now);
}

void dfs_tree_2(long long now)
{
    for (long long i=0;i<e[now].size();i++)
    {
        update_rec_1(e[now][i]);
        dfs_tree_2(e[now][i]);
    }
    if (now!=R)
        update_rec_1(fa[now]);
}

void build_st_rec_d_2(long long now,long long l,long long r);

void build_st_rec_d_1(long long now,long long l,long long r)
{
    long long size=(long long)((1<<int(ceil(log2(r-l+1))+1))+2);
    st_rec_d_l.clear();
    st_rec_d_l.resize(size);
    st_rec_d_r.clear();
    st_rec_d_r.resize(size);
    st_rec_d_mid.clear();
    st_rec_d_mid.resize(size);
    st_rec_d_min.clear();
    st_rec_d_min.resize(size);
    st_rec_d_min_p.clear();
    st_rec_d_min_p.resize(size);
    build_st_rec_d_2(now,l,r);
}

void build_st_rec_d_2(long long now,long long l,long long r)
{
    st_rec_d_l[now]=l;
    st_rec_d_r[now]=r;
    st_rec_d_mid[now]=(l+r)/2;
    if (l==r)
    {
        st_rec_d_min[now]=rec_d[l];
        st_rec_d_min_p[now]=l;
    }
    else if (l<r)
    {
        if (l<=st_rec_d_mid[now])
            build_st_rec_d_2(now*2,l,st_rec_d_mid[now]);
        if (st_rec_d_mid[now]+1<=r)
            build_st_rec_d_2(now*2+1,st_rec_d_mid[now]+1,r);
        if (st_rec_d_min[now*2]<=st_rec_d_min[now*2+1])
        {
            st_rec_d_min[now]=st_rec_d_min[now*2];
            st_rec_d_min_p[now]=st_rec_d_min_p[now*2];
        }
        else
        {
            st_rec_d_min[now]=st_rec_d_min[now*2+1];
            st_rec_d_min_p[now]=st_rec_d_min_p[now*2+1];
        }
    }
}

long long sum_st_rec_d_min_1(long long now,long long l,long long r)
{
    if (st_rec_d_l[now]==l&&r==st_rec_d_r[now])
        return st_rec_d_min[now];
    else if (r<=st_rec_d_mid[now])
        return sum_st_rec_d_min_1(now*2,l,r);
    else if (st_rec_d_mid[now]+1<=l)
        return sum_st_rec_d_min_1(now*2+1,l,r);
    else
        return min(sum_st_rec_d_min_1(now*2,l,st_rec_d_mid[now]),sum_st_rec_d_min_1(now*2+1,st_rec_d_mid[now]+1,r));
}

long long sum_st_rec_d_min_p_1(long long now,long long l,long long r)
{
    if (st_rec_d_l[now]==l&&r==st_rec_d_r[now])
        return st_rec_d_min_p[now];
    else if (r<=st_rec_d_mid[now])
        return sum_st_rec_d_min_p_1(now*2,l,r);
    else if (st_rec_d_mid[now]+1<=l)
        return sum_st_rec_d_min_p_1(now*2+1,l,r);
    else
    {
        if (sum_st_rec_d_min_1(now*2,l,st_rec_d_mid[now])<=sum_st_rec_d_min_1(now*2+1,st_rec_d_mid[now]+1,r))
            return sum_st_rec_d_min_p_1(now*2,l,st_rec_d_mid[now]);
        else
            return sum_st_rec_d_min_p_1(now*2+1,st_rec_d_mid[now]+1,r);
    }
}

void pr_lca_1()
{
    pr_tree_1();
    dfs_tree_1(R);
    build_st_rec_d_1(1,1,rec_d.size()-1);
}

long long lca_1(long long x,long long y)
{
    return rec_p[sum_st_rec_d_min_p_1(1,min(rec_f[x],rec_f[y]),max(rec_f[x],rec_f[y]))];
}

int main()
{
    while (~scanf("%lld%lld",&n,&m))
    {
        for (long long i=1;i<n;i++)
            scanf("%lld%lld%lld",&e_x[i],&e_y[i],&e_d[i]);
        pr_lca_1();
        cnt=ans=0;
        for (long long i=1;i<=m;i++)
        {
            long long x,y;
            scanf("%lld%lld",&x,&y);
            //測試數據好像有問題，處理錯誤
            x=((x<1)?1:x);
            x=((x>n)?n:x);
            y=((y<1)?1:y);
            y=((y>n)?n:y);
            //測試數據好像有問題，處理錯誤
            if (lca_1(x,y)==x)
            {
                cnt++;
                ans+=abs(dis[x]-dis[y]);
            }
        }
        printf("%lld\n",cnt);
        printf("%lld\n",ans);
    }
}

第3個測試點完整數據
輸入
511 500
1 511 7
1 510 4
510 509 5
510 508 6
508 507 1
508 506 9
506 505 8
506 504 10
504 503 7
504 502 5
502 501 6
502 500 9
500 499 8
500 498 4
498 497 10
498 496 3
496 495 3
496 494 7
494 493 10
494 492 9
492 491 1
492 490 9
490 489 6
490 488 8
488 487 5
488 486 10
486 485 9
486 484 3
484 483 2
484 482 7
482 481 8
482 480 3
480 479 8
480 478 4
478 477 6
478 476 6
476 475 7
476 474 9
474 473 8
474 472 7
472 471 1
472 470 10
470 469 4
470 468 1
468 467 1
468 466 9
466 465 8
466 464 1
464 463 4
464 462 10
462 461 3
462 460 10
460 459 3
460 458 6
458 457 9
458 456 3
456 455 3
456 454 10
454 453 1
454 452 8
452 451 3
452 450 9
450 449 9
450 448 3
448 447 5
448 446 8
446 445 5
446 444 9
444 443 6
444 442 9
442 441 1
442 440 3
440 439 8
440 438 3
438 437 3
438 436 6
436 435 9
436 434 2
434 433 1
434 432 3
432 431 10
432 430 8
430 429 2
430 428 7
428 427 7
428 426 10
426 425 5
426 424 2
424 423 5
424 422 4
422 421 1
422 420 7
420 419 3
420 418 3
418 417 9
418 416 10
416 415 6
416 414 3
414 413 3
414 412 2
412 411 7
412 410 10
410 409 7
410 408 4
408 407 5
408 406 3
406 405 4
406 404 9
404 403 9
404 402 5
402 401 4
402 400 3
400 399 6
400 398 7
398 397 1
398 396 9
396 395 1
396 394 2
394 393 3
394 392 5
392 391 8
392 390 9
390 389 7
390 388 2
388 387 2
388 386 10
386 385 6
386 384 8
384 383 8
384 382 10
382 381 1
382 380 4
380 379 6
380 378 10
378 377 3
378 376 2
376 375 1
376 374 8
374 373 7
374 372 10
372 371 10
372 370 6
370 369 7
370 368 7
368 367 3
368 366 10
366 365 7
366 364 4
364 363 1
364 362 1
362 361 2
362 360 5
360 359 7
360 358 7
358 357 9
358 356 4
356 355 8
356 354 2
354 353 10
354 352 10
352 351 4
352 350 9
350 349 7
350 348 3
348 347 6
348 346 1
346 345 5
346 344 8
344 343 3
344 342 6
342 341 4
342 340 8
340 339 7
340 338 9
338 337 9
338 336 4
336 335 2
336 334 8
334 333 9
334 332 6
332 331 8
332 330 9
330 329 7
330 328 7
328 327 8
328 326 4
326 325 10
326 324 3
324 323 2
324 322 2
322 321 6
322 320 2
320 319 9
320 318 5
318 317 5
318 316 4
316 315 9
316 314 6
314 313 5
314 312 3
312 311 1
312 310 2
310 309 9
310 308 4
308 307 7
308 306 10
306 305 1
306 304 8
304 303 2
304 302 7
302 301 10
302 300 7
300 299 7
300 298 8
298 297 1
298 296 8
296 295 4
296 294 6
294 293 7
294 292 4
292 291 3
292 290 5
290 289 6
290 288 3
288 287 7
288 286 10
286 285 9
286 284 9
284 283 2
284 282 7
282 281 7
282 280 7
280 279 4
280 278 8
278 277 2
278 276 2
276 275 7
276 274 7
274 273 4
274 272 7
272 271 9
272 270 6
270 269 5
270 268 6
268 267 10
268 266 7
266 265 9
266 264 6
264 263 1
264 262 10
262 261 9
262 260 4
260 259 3
260 258 9
258 257 10
258 256 3
256 255 3
256 254 4
254 253 3
254 252 3
252 251 8
252 250 6
250 249 5
250 248 1
248 247 8
248 246 6
246 245 2
246 244 8
244 243 2
244 242 7
242 241 8
242 240 7
240 239 5
240 238 1
238 237 7
238 236 7
236 235 4
236 234 3
234 233 10
234 232 7
232 231 8
232 230 7
230 229 2
230 228 10
228 227 10
228 226 6
226 225 7
226 224 1
224 223 2
224 222 6
222 221 3
222 220 1
220 219 8
220 218 8
218 217 2
218 216 4
216 215 5
216 214 10
214 213 4
214 212 6
212 211 2
212 210 3
210 209 3
210 208 7
208 207 8
208 206 7
206 205 4
206 204 5
204 203 1
204 202 6
202 201 3
202 200 10
200 199 5
200 198 7
198 197 3
198 196 6
196 195 4
196 194 10
194 193 5
194 192 8
192 191 1
192 190 3
190 189 7
190 188 1
188 187 10
188 186 1
186 185 4
186 184 8
184 183 5
184 182 8
182 181 8
182 180 1
180 179 3
180 178 5
178 177 10
178 176 7
176 175 6
176 174 8
174 173 4
174 172 8
172 171 2
172 170 1
170 169 7
170 168 3
168 167 3
168 166 4
166 165 1
166 164 2
164 163 6
164 162 9
162 161 9
162 160 10
160 159 4
160 158 1
158 157 1
158 156 5
156 155 4
156 154 6
154 153 6
154 152 9
152 151 8
152 150 10
150 149 4
150 148 10
148 147 4
148 146 6
146 145 6
146 144 1
144 143 5
144 142 8
142 141 10
142 140 8
140 139 5
140 138 4
138 137 1
138 136 5
136 135 10
136 134 4
134 133 10
134 132 6
132 131 8
132 130 2
130 129 5
130 128 6
128 127 3
128 126 1
126 125 7
126 124 1
124 123 10
124 122 3
122 121 9
122 120 5
120 119 9
120 118 5
118 117 7
118 116 2
116 115 3
116 114 9
114 113 2
114 112 8
112 111 5
112 110 9
110 109 9
110 108 1
108 107 9
108 106 6
106 105 10
106 104 7
104 103 3
104 102 6
102 101 8
102 100 1
100 99 6
100 98 4
98 97 2
98 96 4
96 95 9
96 94 10
94 93 9
94 92 4
92 91 8
92 90 7
90 89 10
90 88 3
88 87 10
88 86 7
86 85 5
86 84 5
84 83 4
84 82 9
82 81 5
82 80 6
80 79 10
80 78 8
78 77 5
78 76 8
76 75 1
76 74 2
74 73 3
74 72 9
72 71 6
72 70 3
70 69 1
70 68 8
68 67 4
68 66 5
66 65 2
66 64 5
64 63 5
64 62 7
62 61 10
62 60 5
60 59 1
60 58 2
58 57 2
58 56 8
56 55 1
56 54 9
54 53 9
54 52 7
52 51 10
52 50 3
50 49 10
50 48 6
48 47 6
48 46 6
46 45 8
46 44 8
44 43 3
44 42 9
42 41 10
42 40 2
40 39 5
40 38 7
38 37 10
38 36 10
36 35 1
36 34 10
34 33 2
34 32 3
32 31 8
32 30 6
30 29 2
30 28 9
28 27 6
28 26 1
26 25 8
26 24 1
24 23 4
24 22 2
22 21 6
22 20 3
20 19 5
20 18 8
18 17 7
18 16 3
16 15 7
16 14 6
14 13 8
14 12 9
12 11 6
12 10 7
10 9 2
10 8 5
8 7 9
8 6 2
6 5 1
6 4 8
4 3 2
4 2 2
132 119
494 481
356 343
180 167
228 215
490 477
156 143
512 499
260 247
468 455
280 267
198 185
398 385
164 151
378 365
234 221
162 149
512 499
196 183
141 327
280 267
252 239
370 357
214 201
422 409
412 399
214 201
228 215
310 297
212 199
316 303
398 385
376 363
182 169
264 251
462 449
296 283
506 493
244 231
153 292
470 457
230 217
190 177
238 225
130 117
354 341
298 285
490 477
206 193
162 149
470 457
416 403
124 111
360 347
456 443
352 339
120 107
170 157
308 295
44 352
280 267
160 147
208 195
236 223
124 111
394 381
360 347
304 291
380 367
338 325
444 431
342 329
328 315
412 399
350 337
404 391
246 233
288 275
474 461
4 230
390 377
424 411
410 397
384 371
370 357
466 453
370 357
158 145
300 287
334 321
292 279
166 153
152 139
402 389
216 203
310 297
194 181
182 169
340 327
136 381
236 223
470 457
404 391
478 465
134 121
116 103
268 255
136 123
392 379
346 333
368 355
276 263
406 393
246 233
176 163
426 413
344 331
228 215
126 113
87 220
354 341
230 217
414 401
454 441
190 177
502 489
498 485
148 135
496 483
260 247
370 357
368 355
392 379
114 101
430 417
148 135
364 351
316 303
134 121
37 250
310 297
418 405
152 139
432 419
306 293
116 103
424 411
186 173
298 285
168 155
168 155
374 361
122 109
268 255
338 325
350 337
234 221
378 365
128 115
15 464
250 237
458 445
128 115
452 439
446 433
374 361
372 359
492 479
252 239
304 291
356 343
254 241
244 231
352 339
374 361
272 259
402 389
444 431
226 213
87 468
458 445
452 439
384 371
242 229
426 413
346 333
290 277
268 255
134 121
316 303
236 223
506 493
314 301
188 175
304 291
198 185
292 279
368 355
346 333
139 416
260 247
344 331
344 331
474 461
490 477
118 105
340 327
460 447
332 319
318 305
184 171
330 317
344 331
342 329
268 255
258 245
310 297
218 205
146 133
120 231
458 445
234 221
288 275
448 435
346 333
134 121
400 387
142 129
238 225
300 287
134 121
148 135
402 389
258 245
486 473
146 133
242 229
512 499
344 331
32 370
240 227
154 141
348 335
326 313
198 185
240 227
134 121
208 195
348 335
198 185
120 107
390 377
510 497
282 269
462 449
304 291
286 273
460 447
208 195
133 323
180 167
310 297
386 373
372 359
116 103
284 271
264 251
424 411
292 279
178 165
256 243
330 317
292 279
374 361
358 345
406 393
144 131
362 349
282 269
94 308
114 101
244 231
156 143
474 461
388 375
292 279
404 391
414 401
128 115
472 459
146 133
238 225
474 461
198 185
338 325
442 429
154 141
228 215
502 489
139 476
156 143
126 113
474 461
424 411
414 401
444 431
184 171
188 175
338 325
166 153
240 227
180 167
492 479
460 447
422 409
448 435
322 309
486 473
396 383
41 213
460 447
226 213
168 155
148 135
160 147
202 189
458 445
436 423
470 457
302 289
142 129
242 229
340 327
354 341
178 165
136 123
432 419
116 103
206 193
27 385
308 295
136 123
410 397
232 219
504 491
330 317
196 183
126 113
496 483
336 323
468 455
300 287
322 309
132 119
120 107
120 107
346 333
164 151
212 199
61 467
484 471
388 375
494 481
240 227
264 251
192 179
484 471
400 387
406 393
296 283
350 337
382 369
338 325
310 297
134 121
124 111
274 261
300 287
460 447
40 472
252 239
442 429
340 327
138 125
180 167
438 425
454 441
390 377
200 187
466 453
268 255
468 455
200 187
314 301
246 233
224 211
496 483
470 457
310 297
171 214
410 397
166 153
508 495
254 241
496 483
214 201
504 491
170 157
462 449
172 159
398 385
372 359
440 427
402 389
232 219
190 177
326 313
258 245
390 377
62 475
458 445
122 109
494 481
120 107
144 131
222 209
450 437
176 163
250 237
454 441
432 419
162 149
266 253
286 273
206 193
162 149
436 423
510 497
306 293
17 429
502 489
428 415
350 337
312 299
176 163
288 275
210 197
398 385
186 173
156 143
452 439
196 183
326 313
170 157
232 219
376 363
176 163
396 383
404 391
42 216
464 451
204 191
210 197
320 307
138 125
434 421
496 483
294 281
326 313
470 457
386 373
240 227
176 163
326 313
354 341
138 125
172 159
432 419
506 493
165 435
418 405
296 283
484 471
322 309
218 205
366 353
246 233
500 487
374 361
266 253
492 479
314 301
286 273
256 243
182 169
294 281
432 419
204 191
362 349
189 461
輸出
472
19272

我一开始没有想到要开LongLong，就一直WA三个点，后来看到题解里有人开了longlong ，我就开了，然后就对了，思路有很多，主要还是要自己想
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 214748364
#define DB double
using namespace std;
/*第一行包含三个正整数N、M、S，
分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，
表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
*/
inline ll read()
{
ll x=0,w=1;char ch=0;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;

}
ll h[10005],n,m,tot;
struct po{
ll u,v,c,last;
}a[100005];
void add(ll u,ll v,ll c)
{
tot++;a[tot].u=u;a[tot].c=c;a[tot].v=v;
a[tot].last=h[u];h[u]=tot;
}
ll f[10005][30],dep[10005];
ll d[10005][30];
void dfs(ll u)
{
for(ll i=h[u];i;i=a[i].last)
{
ll to=a[i].v;
if(dep[to]==0)
{
dep[to]=dep[u]+1;
f[to][0]=u;
d[to][0]=a[i].c;
dfs(to);

}

}
}
void YU()
{
for(ll j=1;j<=20;j++)
for(ll i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[f[i][j-1]][j-1];
}
ll ans,dd;
ll lca(ll x,ll y)
{
ll dis,nw,fa;
dis=d[y][20];nw=x;
ll h=dep[y]-dep[x];
for(ll i=0;i<=20;i++)
if((1<<i)&h) y=f[y][i];

for(ll i=20;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
if(x==y) fa=x;
else fa=f[y][0];
if(fa==nw) return dis-d[fa][20];
else return inf;
}
int main()
{
n=read();m=read();
for(ll i=1;i<=n-1;i++)
{
ll x,y,z;
x=read();y=read();z=read();
add(x,y,z);
add(y,x,z);
}
dep[1]=1;f[1][0]=1;
dfs(1);YU();
for(ll i=1;i<=m;i++)
{
ll x,y;
x=read();y=read();
if(dep[x]<=dep[y])
if(lca(x,y)!=inf)

ans++,dd+=lca(x,y);
//if(x==y) ans++;

}
cout<<ans<<endl<<dd;
return 0;
}
/*
6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
4 5

*/

树上倍增。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int n, m;
typedef pair<int, int> pa;
vector<pa> oed[20000];
//vector<pa> ied[20000];
int fan[20][20000];
long long fad[20][20000];
int inn[20000];
int ro;
int dep[20000];
void dde(int x, int k){
    dep[x] = k;
    For2(i, oed[x].begin(), oed[x].end()){
        if (dep[(*i).second] == 0){
            dde((*i).second, k + 1);
        }
    }
}






int main(){
    cin >> n >> m;
    For(i, 1, n - 1) {
        int tkd, tiv, tkq;
        cin >> tkd >> tiv >> tkq;
        oed[tkd].emplace_back(tkq, tiv);
//        ied[tiv].emplace_back(tkq, tkd);
        fan[0][tiv] = tkd;
        fad[0][tiv] = tkq;
//        inn[tiv]++;
    }
//    For(i, 1, n){
//        cout << fan[0][i] << ' ';
//    }
//    cout << ro << endl;
    dde(1, 1);
    fan[0][1] = 1;
    fad[0][1] = 0;
//    For(i, 1, n){
//        cout << dep[i] << ' ';
//    }
//    cout << endl;
    For(i, 1, 19) {
        For(j, 1, n) {
            fan[i][j] = fan[i - 1][fan[i - 1][j]];
            fad[i][j] = fad[i - 1][j] + fad[i - 1][fan[i - 1][j]];
        }
    }
//    For(i, 1, n){
//        cout << fad[1][i] << ' ';
//    }
    long long ans = 0;
    long long he;
    int num = 0;
    int p, q;
    For(i, 1, m){
        he = 0;
        cin >> p >> q;
        if (dep[p] > dep[q]){
            continue;
        }
        int t = dep[q] - dep[p];
        For(j, 0, 19){
            if ((t >> j) & 1){
                he += fad[j][q];
                q = fan[j][q];
            }
        }
//        cout << he << endl;
        if (p == q) {
            ans += he;
            num++;
        }
    }

    cout << num << endl;
    cout << ans << endl;
//    For(i, 1, 20){
//        cout << (1 << i) << endl;
//    }
    return 0;

}
/*
 *
 *
6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
1 6


6 1
 1 2 1
 2 3 1
 3 4 1
 4 5 1
 5 6 1
 1 6


 */

倍增即可。如果满足题目中的条件，则后面输入的u,v，必然deep[u]<=deep[v].然后v开始往上面跳，当到同一深度时如果u==v合法，否则不合法。代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#define MAXN 10005
using namespace std;

struct edge
{
int to,next,w;
}e[MAXN<<1];

int deep[MAXN],head[MAXN],vis[MAXN];
int n,m,tot=0;
long long tsum=0,ans=0;
long long g[MAXN][22],f[MAXN][22];

inline void adde(int u,int v,int w)
{
e[++tot].to=v;
e[tot].next=head[u];
e[tot].w=w;
head[u]=tot;
}

inline void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=20;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1];
}
for(int i=head[x];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
f[v][0]=x;
g[v][0]=e[i].w;
deep[v]=deep[x]+1;
dfs(v);
}
}
}

inline void lca(int a,int b)
{
long long temp=0;
if(deep[a]<=deep[b])
{
int d=deep[b]-deep[a];
for(int i=20;i>=0;i--)
{
if(d&(1<<i))
{
temp+=g[b][i];
b=f[b][i];
}
}
if(a==b)
{
ans++;
tsum+=temp;
}
}

return ;
}

int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
adde(a,b,t);
}
dfs(1);
for(int i=1,a,b;i<=m;i++)
{
scanf("%d%d",&a,&b);
lca(a,b);
}
printf("%I64d\n%I64d",ans,tsum);
return 0;
}

100AC留念，tarjan的活用
```c++
#include <bits/stdc++.h>
using namespace std;

#define ll long long
struct p {
int to, next;
long long dis;
}edge[10005];
int head[10005], top = 0;
void push(int i, int j, ll dis)
{
edge[++top].to = j;
edge[top].dis = dis;
edge[top].next = head[i];
head[i] = top;
}

int ufset[10005];
inline int fa(int i)
{
return ufset[i]?ufset[i]=fa(ufset[i]):i;
}
inline bool linked(int i, int j)
{
return fa(i) == fa(j);
}
inline void link(int i, int j)
{
if (!linked(i, j))
ufset[fa(i)] = fa(j);
}

int n, m, x[100005], y[100005], rd[10005];
ll dis[10005];
int ans1 = 0;
ll ans2 = 0;

void dfs(int nd)
{
for (int i = head[nd]; i; i = edge[i].next) {
dis[edge[i].to] = dis[nd] + edge[i].dis;
dfs(edge[i].to);
link(nd, edge[i].to);
}
for (int i = 1; i <= m; i++)
if (x[i] == nd && linked(nd, y[i])) {
ans1++;
ans2 += dis[y[i]]-dis[nd];
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(ufset, 0, sizeof ufset);
memset(head, 0, sizeof head);
memset(rd, 0, sizeof rd);
memset(dis, 127, sizeof dis);
int f, t, rt;
ll d;
for (int i = 1; i < n; i++) {
scanf("%d%d%lld", &f, &t, &d);
push(f, t, d);
rd[t]++;
}
for (int i = 1; i <= n; i++)
if (!rd[i]) {
rt = i;
break;
}
for (int i = 1; i <= m; i++)
scanf("%d%d", &x[i], &y[i]);
dis[rt] = 0;
dfs(rt);
cout << ans1 << endl;
cout << ans2 << endl;
return 0;
}
```

这一道题有多种做法，LCA是其中一种，在这就不多讲。其实有种更好的方法，即运用遍历的方法去求x是否是y的父亲。在遍历是，我们把到达某个节点和搜完这个节点及其子树时，记录次序即可。begin[i]表示到这个节点的时间，end[i]表示搜完这个节点及其子树的时间。Begin,end其实就是这一棵树的前序和后序遍历。根据前序和后序遍历的特点可得当且仅当begin[x]<begin[y],end[x]>end[y]时，x是y的父亲。至于距离，在遍历时顺便求出顶点到各个点的距离f[i]，x到y的距离就是f[y]-fx。

测试数据 #0: Accepted, time = 0 ms, mem = 1668 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1668 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1672 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1672 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1668 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 1680 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 1820 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1700 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1672 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1820 KiB, score = 10
Accepted, time = 247 ms, mem = 1820 KiB, score = 100
最后总赛道和总时间应该定为int64

先记忆点到点的路径所用的时间！最后直接询问吗m次是否通！通就记一次，并累加时间！
var
fa,r,t:array[0..10001] of longint;
a:array[1..10000,0..10000] of longint;
x,y,z,n,m,i,j:longint;
time,sum:int64;
begin
assign(input,'p1460.in');
reset(input);
readln(n,m);
fillchar(fa,sizeof(fa),0);
for i:=1 to n-1 do
begin
readln(x,y,z);
t[y]:=z;
fa[y]:=x;
end;
fillchar(a,sizeof(a),0);
for i:=n downto 1 do
begin
x:=i;y:=0;
while x<>0 do
begin
a[i,fa[x]]:=t[x]+y;
y:=a[i,fa[x]];
x:=fa[x];
end;
end;
time:=0;
sum:=0;
for i:=1 to m do
begin
readln(x,y);
if a[y,x]<>0 then
begin
inc(sum);
time:=time+a[y,x];
end;
end;
writeln(sum);
writeln(time);
close(input);
end.

时间戳真的很好用啊。。。

#include<iostream>
#include<cstdio>
using namespace std;

//use of questi on;
int n,m;
int times[10000+5];

//use of line star
int first[10000+5]={0};
int to[10000+5]={0};
int ne[10000+5]={0};

//use of tree
int pre[10000+5]={0};
int back[10000+5]={0};
//use to find root
int judge[10000+5]={0};

//use of memory
int mem[10000+5]={0};

//use to count times
int num[2]={0};

void dfs(int po,int deep)
{
num[0]++;
pre[po]=num[0];
mem[po]=deep;
int temp=first[po];
while(temp!=0)
{
dfs(to[temp],deep+times[temp]);
temp=ne[temp];

}
num[1]++;
back[po]=num[1];
}

int main()
{
scanf("%d%d",&n,&m);

int t1,t2,t3;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
ne[i]=first[t1];
first[t1]=i;
to[i]=t2;
times[i]=t3;
judge[t2]=1;
}
int root=0;
for(int i=1;i<=n;i++)
if(judge[i]==0)
{
root=i;
break;

}

dfs(root,0);

int u,v;
unsigned long long ans=0,ans_t=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);

if((pre[u]<pre[v])&&(back[u]>back[v]))
{
ans++;
ans_t+=mem[v]-mem[u];

}
}

cout<<ans<<endl<<ans_t;

//while(1);
return 0;

}

NOIP2015纪念

一开始看错题目了……直接手码倍增LCA。后来才发现不用……

附赠longlong读入加速一份

/* @AwD 2015 */
#include<cstdio>
#define lowbit(x) ((x)&(-(x)))
typedef long long L64;
int endfile;
L64 getL()
{
L64 t=0, fh=1;
char ch;
int start=0;
while (true)
{
ch=getchar();
if (ch==EOF) {endfile=1; break;}
else if (((ch==' ')||(ch=='\n'))&&(start)) break;
else if (ch=='-') fh=-1;
else if ((ch<='9')&&(ch>='0')) {start=1; t=t*10+ch-'0';}
}
return t*fh;
}
void putL(L64 t)
{
if (t<0) {t*=-1; putchar('-');}
if (t==0) putchar('0');
L64 p=1;
while (p<=t) p*=10;
while (p>=10) {p/=10; putchar(t/p+'0'); t%=p;}
}
int n, m;
int lt[21000], nt[21000], bi[21000];
L64 ci[21000];
int hi[21000], fa[21000], fp[21000];
L64 fad[21000], fpd[21000];
int shed[21000], top=-1;
L64 shedd[21000];
int ans;
L64 sum;
void dfs(int t, int dd)
{
top++;
shed[top]=t; shedd[top]=dd;
hi[t]=top;
if (top)
{
fa[t]=shed[top-1]; fad[t]=shedd[hi[t]]-shedd[hi[fa[t]]];
fp[t]=shed[top-lowbit(top)]; fpd[t]=shedd[hi[t]]-shedd[hi[fp[t]]];
}
for (int p=lt[t]; p!=0; p=nt[p]) dfs(bi[p], dd+ci[p]);
shed[top]=0; shedd[top]=0;
top--;
}
L64 run(int a, int b)
{
int p=a, q=b;
L64 ansi=0;
while (p!=q)
{
if (hi[p]>hi[q])
{
if (hi[fp[p]]>hi[q]) p=fp[p];
else p=fa[p];
}
else if (hi[p]<hi[q])
{
if (hi[p]<hi[fp[q]]) {ansi+=fpd[q]; q=fp[q];}
else {ansi+=fad[q]; q=fa[q];}
}
else
{
if (fp[p]!=fp[q]) {ansi+=fpd[q]; p=fp[p]; q=fp[q];}
else {ansi+=fad[q]; p=fa[p]; q=fa[q];}
}
}
if (p==a) {sum+=ansi; ans++;}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=n-1; ++i)
{
int a, b;
L64 t;
scanf("%d%d", &a, &b); t=getL();
nt[i]=lt[a]; lt[a]=i; bi[i]=b; ci[i]=t;
}
dfs(1, 0);
for (int i=1; i<=m; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
run(a, b);
}
printf("%d\n", ans);
putL(sum);
}

测试数据 #0: Accepted, time = 0 ms, mem = 1728 KiB, score = 10
测试数据 #1: Accepted, time = 1 ms, mem = 1728 KiB, score = 10
测试数据 #2: Accepted, time = 1 ms, mem = 1732 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1780 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1728 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 1816 KiB, score = 10
测试数据 #6: Accepted, time = 125 ms, mem = 2344 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 1876 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 1724 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 2344 KiB, score = 10

倍增法>_<
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define maxn 10010
using namespace std;
typedef long long LL;
int n,head[maxn],h[maxn],d[maxn][20];
LL dis[maxn];
struct EDGE{
int u,v,next;
LL w;
}edge[maxn];
void bfs(){
queue<int>Q;
Q.push(1);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=head[u];i;i=edge[i].next){

EDGE e=edge[i];
int v=e.v;
h[v]=h[u]+1;

d[v][0]=u;
dis[v]=dis[u]+e.w;
Q.push(v);

}
}
}
int lca(int u,int v){
if(u==v)return u;
if(d[u][0]==d[v][0])return d[u][0];
if(h[u]<h[v])return lca(u,d[v][(int)log2(h[v]-h[u])]);
int l=log2(h[u]);
while(d[u][l]==d[v][l])l--;
return lca(d[u][l],d[v][l]);
}
int main(){
freopen("p1460.in","r",stdin);
freopen("wode.out","w",stdout);
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int a,b;
LL c;
scanf("%d%d",&a,&b);
cin>>c;

edge[i]=(EDGE){a,b,head[a],c};
head[a]=i;
}
bfs();
for(int j=1;j<=20;j++){
int l=j-1;
for(int i=1;i<=n;i++){
d[i][j]=d[d[i][j-1]][j-1];
if(d[i][j])l=j;
}
if(l!=j)break;
}

int cnt=0;
LL tot=0;
while(m--){
int a,b;
scanf("%d%d",&a,&b);
if(h[a]>h[b])continue;
if(lca(a,b)==a){
cnt++;
tot+=dis[b]-dis[a];
}
}
printf("%d\n",cnt);
cout<<tot<<endl;
return 0;
}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program ex;

type arr=array[1..10000]of longint;

var i,j,n,m,tolstep,toltime:longint;

child,time:arr;

b,e:array[1..100000]of longint;

mark_pre, mark_now : arr;

start_step, finish_step: arr;

node_time:arr;

ans1,ans2:int64;

procedure init;

var i,j,x,y,z:longint;

begin

readln(n,m);

for i:=1 to n-1 do

begin

readln(x,y,z);

mark_pre[i]:=mark_now[x];

mark_now[x]:=i;

child[i]:=y;

time[i]:=z;

end;

for i:=1 to m do readln(b[i],e[i]);

end;

procedure dfs(node,toltime:longint);

var i,j:longint;

begin

i:=mark_now[node];

inc(tolstep);

start_step[node]:=tolstep;

node_time[node]:=toltime;

while i0 do

begin

dfs(child[i],toltime+time[i]);

i:=mark_pre[i];

end;

inc(tolstep);

finish_step[node]:=tolstep;

end;

procedure main;

var i,j:longint;

begin

tolstep:=0;

dfs(1,0);

for i:=1 to m do

if (start_step[b[i]]finish_step[e[i]]) then

begin

inc(ans1);

inc(ans2,node_time[e[i]]-node_time[b[i]]);

end;

end;

begin

init;

ans1:=0;

ans2:=0;

main;

writeln(ans1);

writeln(ans2);

end.

时间戳，很好！ 图论的算法还真多奇妙的地方。

至于递归的栈，节俭一下还是可以勉强过的，铺张浪费就等着被爆吧……

不用写非递归，记得用int64