Codeforces 191C Fools and Roads

题目链接http://codeforces.com/problemset/problem/191/C

题意:给你一棵树,每棵树初始边权都为0,然后有k次操作,每次操作指定两个点uv,把uv路径上所有边边权加一,问最后树上每条边边权是多少,输出按输入的顺序输出。

思路:比较简单的树上差分,就是输出有点麻烦,因为是边权不是点权,我们是要以深度较深的那个点作为这条边的边权,自己想复杂了。。。其实可以先存边,然后输出的时候判断一下那个深度深就好了。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
int n,i,u,v,k,rt,id[N],dep[N],bel[N],son[N],sz[N],fa[N],val[N];
vector<int>G[N];
vector<pair<int,int> >e;
void dfs(int u,int f){
    sz[u]=1,son[u]=-1,fa[u]=f,dep[u]=dep[f]+1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);  
    }
}
int lca(int x,int y){
    for (;bel[x]!=bel[y];dep[bel[x]]>dep[bel[y]]?x=fa[bel[x]]:y=fa[bel[y]]);
    return dep[x]>dep[y]?y:x;
}
void dfs3(int u,int f){
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs3(v,u);
        val[u]+=val[v];
    }
}
int main(){
    read(n);
    for (i=1;i<n;i++){
        read(u),read(v);
        G[u].push_back(v);
        G[v].push_back(u);
        e.push_back(make_pair(u,v));
    }
    dfs(1,0);
    dfs2(1,1);
    for (i=0;i<n-1;i++){
        int u=e[i].first,v=e[i].second;
        if (dep[u]<dep[v]) id[i+1]=v;
        else id[i+1]=u;
    }
    for (read(k);k--;){
        read(u),read(v);
        rt=lca(u,v);
        val[u]++,val[v]++,val[rt]-=2;
    }
    dfs3(1,0);
    for (i=1;i<n;i++){
        printf("%d%c",val[id[i]],i==n-1?'\n':' ');
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注