题解

72 条题解

  • 3
    @ 2015-08-20 13:36:06

    感觉这道题挺不错的
    一开始用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 的邻接矩阵也能过,但毕竟不是完美方法。

  • 2
    @ 2017-11-02 18:48:25

    写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);
    }
    
  • 2
    @ 2016-07-19 21:54:35

    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);
    }

  • 1
    @ 2019-05-13 20:47:43

    虽然时间复杂度高,但是还是卡着时间过了,最慢的点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;
    }
    
  • 1
    @ 2018-08-29 08:47:40

    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;
    }
    
  • 0
    @ 2020-06-03 09:43:05

    有点意思。。。

  • 0
    @ 2017-10-28 14:23:30

    第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

  • 0
    @ 2017-10-21 18:33:26

    我一开始没有想到要开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

    */

  • 0
    @ 2017-10-03 14:14:22

    树上倍增。

    #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
    
    
     */
    
  • 0
    @ 2016-10-09 11:47:51

    倍增即可。如果满足题目中的条件,则后面输入的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;
    }

  • 0
    @ 2016-08-16 11:35:34

    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;
    }
    ```

  • 0
    @ 2016-07-09 20:23:09

    这一道题有多种做法,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
    @ 2015-12-20 09:27:07

    测试数据 #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

    • @ 2016-07-09 20:23:47

      一开始WA了5次!!/(ㄒoㄒ)/~~

  • 0
    @ 2015-12-03 23:27:49

    先记忆点到点的路径所用的时间!最后直接询问吗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.

  • 0
    @ 2015-11-27 18:43:42

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

    #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;

    }

  • 0
    @ 2015-11-06 10:52:38

    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

  • 0
    @ 2015-08-11 16:28:16

    倍增法>_<
    #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;
    }

  • 0
    @ 2009-11-08 20:25:42

    编译通过...

    ├ 测试数据 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.

  • 0
    @ 2009-11-04 11:48:58

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

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

  • 0
    @ 2009-10-27 07:54:03

    不用写非递归,记得用int64

信息

ID
1460
难度
7
分类
树结构 | 最近公共祖先 点击显示
标签
递交数
1766
已通过
341
通过率
19%
被复制
3
上传者