题解

18 条题解

  • 4
    @ 2017-10-16 22:42:21
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int root=1;
    const int MAXN=300033;
    struct Edge{
        int nx,to,val;
        Edge(){}
        Edge(int nx,int to,int val):nx(nx),to(to),val(val){}
    }E[MAXN<<1];
    int first[MAXN],ecnt=1;
    inline void addedge(int f,int t,int val)
    {
        E[++ecnt]=Edge(first[f],t,val);first[f]=ecnt;
        E[++ecnt]=Edge(first[t],f,val);first[t]=ecnt;
    }
    int n,m;
    int dep[MAXN],f[21][MAXN],dis[MAXN];
    int sum[MAXN];
    int l=0,r=0,mid,ans;
    int Length[MAXN];
    void LCA_INIT(int e)
    {
        int r;
        for(int i=1;i<=20;++i)
            f[i][e]=f[i-1][f[i-1][e]];
        for(int i=first[e];i;i=E[i].nx)
        {
            if((r=E[i].to)==f[0][e]) continue;
            dep[r]=dep[e]+1;
            f[0][r]=e;
            Length[r]=E[i].val;
            dis[r]=dis[e]+E[i].val;
            LCA_INIT(r);
        }
    }
    int LCA(int l,int r)
    {
        if(dep[r]<dep[l]) swap(l,r);
        for(int i=20;i>=0;--i)
        {
            if(dep[r]-(1<<i)<dep[l]) continue;
            r=f[i][r];
        }
        if(l==r) return r;
        for(int i=20;i>=0;--i)
        {
            if(f[i][r]==f[i][l]) continue;
            r=f[i][r];l=f[i][l];
        }
        return f[0][r];
    }
    struct Stage{
        int l,r;
        int LCA,len;
    }S[MAXN];
    
    void Push(int e)
    {
        int r;
        for(int i=first[e];i;i=E[i].nx)
        {
            if((r=E[i].to)==f[0][e]) continue;
            Push(r);
            sum[e]+=sum[r];
        }
    }
    
    inline bool check()
    {
        memset(sum,0,sizeof sum);
        int MX=0,cnt=0;
        for(int i=1;i<=m;++i)
        {
            if(S[i].len>mid)
            {
                ++sum[S[i].l];
                ++sum[S[i].r];
                sum[S[i].LCA]-=2;
                MX=max(MX,S[i].len-mid);
                ++cnt;
            }
        }
        Push(root);
        for(int i=1;i<=n;++i) if(sum[i]==cnt&&Length[i]>=MX) return true;
        return false;
    }
    
    
    int main()
    {
        int x,y,z;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            addedge(x,y,z);
            r+=z;
        }
        dep[root]=1;
        LCA_INIT(root);
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d",&S[i].l,&S[i].r);
            S[i].LCA=LCA(S[i].l,S[i].r);
            S[i].len=dis[S[i].l]+dis[S[i].r]-(dis[S[i].LCA]<<1);
        }
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check()) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d",ans);
        return 0;
    }
    
    • @ 2021-12-19 12:53:05

      你这题解不能碰,一碰就WAQAQ

  • 3
    @ 2017-10-25 21:12:21

    先用lca求出每种运输计划的长度,然后按长度从长到短对每种运输计划排序。二分答案,先找到有多少条运输计划长度比答案长,记录为last,然后对这些比答案长的运输计划进行树上差分,再dfs求树上前缀和。对所有经过次数为last的边找最大值maxn,再用最长的计划减去maxn看是否小于等于答案。
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,m,a[300005],c,dis[300005],d[300005],f[300005][20],maxm,tree[300005],last,maxn;
    struct node{
    int next,to,w;
    }b[600005];
    struct edge{
    int u,v,z,l;
    }e[300005];
    void add(int x,int y,int z){
    b[++c].to=y;
    b[c].next=a[x];
    b[c].w=z;
    a[x]=c;
    b[++c].to=x;
    b[c].next=a[y];
    b[c].w=z;
    a[y]=c;
    }
    void dfs(int x,int from){
    for(int i=a[x];i;i=b[i].next){
    int y=b[i].to;
    if(y==from)continue;
    d[y]=d[x]+1;
    dis[y]=dis[x]+b[i].w;
    f[y][0]=x;
    dfs(y,x);
    }
    }
    int lca(int x,int y){
    if(d[x]>d[y])swap(x,y);
    int l=d[y]-d[x];
    for(int i=19;i>=0;i--){
    if((1<<i)&l)y=f[y][i];
    }
    if(x!=y){
    for(int i=19;i>=0;i--){
    if(f[x][i]!=f[y][i]){
    x=f[x][i];
    y=f[y][i];
    }
    }
    x=f[x][0];
    }
    return x;
    }
    bool cmp(edge a,edge b){
    return a.l>b.l;
    }
    void dfs2(int x,int from){
    for(int i=a[x];i;i=b[i].next){
    int y=b[i].to;
    if(y==from)continue;
    dfs2(y,x);
    tree[x]+=tree[y];
    }
    if(tree[x]==last){
    if(dis[x]-dis[from]>maxn)maxn=dis[x]-dis[from];
    }
    }
    bool judge(int x){
    memset(tree,0,sizeof(tree));
    last=m;
    for(int i=1;i<=m;i++){
    if(e[i].l>x){
    tree[e[i].u]++;
    tree[e[i].v]++;
    tree[e[i].z]-=2;
    }
    else {
    last=i-1;
    break;
    }
    }
    maxn=0;
    dfs2(1,0);
    if(e[1].l-maxn<=x)return true;
    return false;
    }
    int main(){
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);
    }
    dfs(1,0);
    for(int j=1;j<=19;j++)
    for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=m;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    int z=lca(x,y);
    int l=dis[x]+dis[y]-2*dis[z];
    e[i].l=l;
    e[i].u=x;
    e[i].v=y;
    e[i].z=z;
    maxm=max(maxm,l);
    }
    sort(e+1,e+m+1,cmp);
    int left=0,right=maxm;
    while(left<right){
    /*if(right-left==1){
    if(judge(right))left=right;
    break;
    }*/
    int mid=(left+right)/2;
    if(judge(mid))right=mid;
    else left=mid+1;
    }
    cout<<left<<endl;
    }

  • 2
    @ 2016-11-14 19:56:20

    二份答案+LCA
    迷之卡时,“被逼无奈”写了读入优化

    
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cctype>
    #include <algorithm>
    using namespace std;
    #define N 700100
    struct node {
        int to,next,w;
    }e[N];
    template<typename T>
    inline void read(T &x) {
        char ch;
        while ( !isdigit((ch=getchar())) );
        for (x=ch-'0';isdigit((ch=getchar()));x=(x<<3)+(x<<1)+ch-'0');
        ungetc(ch,stdin);
        
    }
    int head[N],dep[N],n,m,tot = 0,cnt;
    int s[N][20],sum[N],dis[N],dist[N];
    int A[N],B[N],LCA[N],fa[N],v[N];
    void add(int u,int v,int w) {
        e[tot].to = v; e[tot].w = w; e[tot].next = head[u];
        head[u] = tot++;
        e[tot].to = u; e[tot].w = w;e[tot].next = head[v];
        head[v] = tot++;
    }
    void dfs(int x) {
        for (int i=head[x];~i;i=e[i].next)
            if ( e[i].to != fa[x] ) {
                dep[e[i].to] = dep[x] + 1;
                fa[e[i].to] = x;
                v[e[i].to] = e[i].w;
                dis[e[i].to] = dis[x] + e[i].w;
                dfs(e[i].to);
            }
    }
    int lca(int x,int y) {
        if ( dep[x] > dep[y] ) swap(x,y);
        for (int i=19;i>=0;i--)  
            if ( dep[y] - dep[x] >= (1<<i) ) {
                y = s[y][i];
            }
        if ( x == y ) return x; 
        for (int i=19;i>=0;i--) 
            if ( s[x][i] != s[y][i] ) {
                x = s[x][i];
                y = s[y][i];
            }
        return fa[x];   
    }
    void what(int x) {
        for (int i=head[x];~i;i=e[i].next)
            if ( e[i].to != fa[x] ) {
                what(e[i].to);
                sum[x] += sum[e[i].to];
            }
    }
    bool check(int x) {
        int dec = 0; cnt = 0;
        for (int i=1;i<=n;i++) sum[i] = 0;
        for (int i=1;i<=m;i++)
            if ( dist[i] > x ) {
                cnt ++;
                dec = max(dec,dist[i]-x);
                sum[A[i]] ++;
                sum[B[i]] ++;
                sum[LCA[i]] -= 2;
            }
        what(1);
        for (int i=1;i<=n;i++)
        if ( (sum[i] == cnt ) && ( v[i] >= dec ) ) return 1;
        return 0;
    }
    int main() {
        int a,b,c;
        memset(head,-1,sizeof head);
        read(n); read(m);
        for (int i=1;i<n;i++) {
            read(a);read(b);read(c);
            add(a,b,c);
        }
        dfs(1);
        for (int i=1;i<=n;i++) s[i][0] = fa[i];
        for (int h=1;h<20;h++)
            for (int i=1;i<=n;i++)
                s[i][h] = s[s[i][h-1]][h-1];
        for (int i=1;i<=m;i++) {
            read(A[i]); read(B[i]);
            LCA[i] = lca(A[i],B[i]);
            //cout<<LCA[i]<<endl;
            dist[i] = dis[A[i]] + dis[B[i]] - 2*dis[LCA[i]];
        }
        int L = 0,R = 0;
        for (int i=1;i<=m;i++)
            R = max(R,dist[i]);
        int mid;
        while ( L <= R ) {
            mid = ( L + R ) >> 1;
            if ( check(mid) ) R = mid - 1;
            else L = mid + 1;
        }
        cout<<L<<endl;
        return 0;
    } 
    
    
  • 1
    @ 2018-08-20 09:13:38
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    #define MAXN 300010
    using namespace std;
    
    int N,M;
    
    struct edge
    {
        int u,v;
        int w;
    } E[MAXN<<1];
    int EC=0,Ef[MAXN<<1],En[MAXN<<1];
    
    void inline ADD_EDGE(int u,int v,int w)
    {
        E[++EC].u=u; E[EC].v=v; E[EC].w=w;
        En[EC]=Ef[u]; Ef[u]=EC; 
    }
    
    struct query
    {
        int u,v;
        int LCA;
        int l;
        bool operator > (const query& q) const
        {
            return l>q.l;
        }
    } Q[MAXN<<1];
    int Qf[MAXN<<1],Qn[MAXN<<1]; 
    
    void inline ADD_QUERY(int u,int v,int i)
    {
        Q[i].u=u; Q[i].v=v; Q[i].LCA=Q[i].l=0;
        Qn[(i<<1)]=Qf[u]; Qf[u]=(i<<1);
        Qn[(i<<1)|1]=Qf[v]; Qf[v]=(i<<1)|1;
    }
    
    int dist[MAXN],P[MAXN],visited[MAXN],nw[MAXN],fa[MAXN];
    
    int FIND_SET(int u)
    {
        if(P[u]==u) return u;
        else return P[u]=FIND_SET(P[u]);
    }
    
    void DFS(int u)
    {
        P[u]=u;
        for(int i=Ef[u];i;i=En[i])
        {
            edge& e=E[i];
            if(e.v!=fa[u])
            {
                dist[e.v]=dist[u]+e.w;
                nw[e.v]=e.w;
                fa[e.v]=u;
                DFS(e.v);
                P[e.v]=u;
            }
        }
        visited[u]=true;
        for(int i=Qf[u];i;i=Qn[i])
        {
    
            query& q=Q[i>>1];
            if(!q.LCA)
            {
                if(q.v==u) swap(q.u,q.v);
                if(visited[q.v])
                {
                    q.LCA=FIND_SET(q.v);
                    q.l=dist[u]+dist[q.v]-2*dist[FIND_SET(q.v)];
                }
            }
        }
    }
    
    int inline Q_FIND(int minl)
    {
        int l=1,u=M;
        while(l<u)
        {
            int m=(l+u+1)>>1;
            if(Q[m].l>minl) l=m;
            else u=m-1;
        }
        return l;
    }
    
    int tot,cnt[MAXN],rtn[MAXN],min_nw;
    
    bool CHECK_DFS(int u)
    {
        rtn[u]=cnt[u];
        for(int i=Ef[u];i;i=En[i])
        {
            edge& e=E[i];
            if(e.v!=fa[u])
            {
                //fa[]在预处理DFS时已建立完成 
                if(CHECK_DFS(e.v)) return true;
                rtn[u]+=rtn[e.v];
            }
        }
        return (rtn[u]>=tot&&nw[u]>=min_nw);
    }
    
    bool inline CHECK(int t)
    {
        memset(cnt,0,sizeof(cnt));
        tot=Q_FIND(t);
        for(int i=1;i<=tot;i++)
        {
            cnt[Q[i].u]++;
            cnt[Q[i].v]++;
            cnt[Q[i].LCA]-=2;
        }
        min_nw=Q[1].l-t;
        return CHECK_DFS(1);
    }
    
    int MAX_W=0;
    
    int main()
    {
        memset(Ef,0,sizeof(Ef));
        memset(Qf,0,sizeof(Qf));
    
        scanf("%d%d",&N,&M);
        int u,v,w,l,m;
        for(int i=1;i<N;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            MAX_W=max(MAX_W,w);
            ADD_EDGE(u,v,w);
            ADD_EDGE(v,u,w);
        }
        for(int i=1;i<=M;i++)
        {
            scanf("%d%d",&u,&v);
            ADD_QUERY(u,v,i);
        }
    
        memset(visited,false,sizeof(visited));
        dist[1]=0; nw[1]=0; fa[1]=1;
        DFS(1);
    
        sort(Q+1,Q+1+M,greater<query>());
    
        l=Q[1].l-MAX_W;
        u=Q[1].l-1;
        while(l<u)
        {
            m=(l+u)>>1;
            if(CHECK(m)) u=m;
            else l=m+1;
        }
    
        printf("%d\n",l);
    
        return 0;
    }
    
  • 1
    @ 2017-07-28 19:37:15

    NOIP2015Day1T3
    有些难
    找到两个好东西:
    1. 给力的题解-> https://blog.sengxian.com/solutions/noip-2015-day2
    2. 给力的UOJ-> http://uoj.ac/problem/150 (Vjios本题的数据略有些水)

    然后贴两份代码,一个在UOJ超时,一个KA常数成功(Vijos测大约快2倍),这让我明白了为什么很多标算都是写bfs的了。

    代码1:
    UOJ:95分 AC*19 TLE*1
    Vijos:100分 AC*20

    #pragma comment(linker, "/STACK:10240000,10240000")
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    using namespace std;
    const int N=300000+5,M=N*2,Inf=N*1000;
    void read(int &x){
        x=0;
        char ch=getchar();
        while (!('0'<=ch&&ch<='9'))
            ch=getchar();
        while ('0'<=ch&&ch<='9'){
            x=x*10+ch-48;
            ch=getchar();
        }
    }
    struct Edge{
        int cnt,y[M],z[M],nxt[M],fst[N];
        void set(){
            cnt=0;
            memset(y,0,sizeof y);
            memset(z,0,sizeof z);
            memset(nxt,0,sizeof nxt);
            memset(fst,0,sizeof fst);
        }
        void add(int a,int b,int c){
            cnt++;
            y[cnt]=b,z[cnt]=c;
            nxt[cnt]=fst[a],fst[a]=cnt;
        }
    }e;
    int n,m;
    vector <int> Tree[N];
    int father[N],son[N],deep[N],dis[N],fadis[N];
    int Anst[N][20];//Ancestor
    struct Query{
        int x,y,LCA,cost;
    }q[N];
    int Nextsum[N];
    void Build_Tree(int prev,int rt){
        Tree[rt].clear(),deep[rt]=deep[prev]+1,son[rt]=0,Anst[rt][0]=father[rt]=prev;
        for (int i=1;(1<<i)<=deep[rt];i++)
            Anst[rt][i]=Anst[Anst[rt][i-1]][i-1];
        for (int i=e.fst[rt];i;i=e.nxt[i])
            if (e.y[i]!=prev){
                son[rt]++,Tree[rt].push_back(e.y[i]),
                fadis[e.y[i]]=e.z[i],dis[e.y[i]]=dis[rt]+e.z[i];
                Build_Tree(rt,e.y[i]);
            }
    }
    int LCA(int a,int b){
        if (deep[a]>deep[b])
            swap(a,b);
        for (int i=deep[b]-deep[a],j=0;i>0;i>>=1,j++)
            if (i&1)
                b=Anst[b][j];
        if (a==b)
            return a;
        int k;
        for (k=0;(1<<k)<=deep[a];k++);
        for (;k>=0;k--)
            if ((1<<k)<=deep[a]&&Anst[a][k]!=Anst[b][k])
                a=Anst[a][k],b=Anst[b][k];
        return Anst[a][0];
    }
    void Get_Nextsum(int rt){
        for (int i=0;i<son[rt];i++){
            Get_Nextsum(Tree[rt][i]);
            Nextsum[rt]+=Nextsum[Tree[rt][i]];
        }
    }
    bool check(int t){
        int total=0,Maxcost=0,Maxcut=0;
        memset(Nextsum,0,sizeof Nextsum);
        for (int i=1;i<=m;i++)
            if (q[i].cost>t){
                Maxcost=max(Maxcost,q[i].cost-t);
                total++;
                Nextsum[q[i].x]++;
                Nextsum[q[i].y]++;
                Nextsum[q[i].LCA]-=2;
            }
        Get_Nextsum(1);
        for (int i=1;i<=n;i++)
            if (Nextsum[i]==total)
                Maxcut=max(Maxcut,fadis[i]);
        return Maxcost<=Maxcut;
    }
    int main(){
        read(n),read(m);
        e.set();
        int Csum=0;
        for (int i=1;i<n;i++){
            int a,b,c;
            read(a),read(b),read(c);
            e.add(a,b,c);
            e.add(b,a,c);
            Csum+=c;
        }
        deep[0]=-1,dis[1]=fadis[1]=0;
        memset(Anst,0,sizeof Anst);
        Build_Tree(0,1);
        for (int i=1;i<=m;i++){
            read(q[i].x),read(q[i].y);
            q[i].LCA=LCA(q[i].x,q[i].y);
            q[i].cost=dis[q[i].x]+dis[q[i].y]-dis[q[i].LCA]*2;
        }
        int le=0,ri=Csum,mid,ans=0;
        while (le<=ri){
            mid=(le+ri)>>1;
            if (check(mid))
                ri=mid-1,ans=mid;
            else
                le=mid+1;
        }
        printf("%d",ans);
        return 0;
    }
    
    

    代码2:
    UOJ:100分 AC*20
    Vijos:100分 AC*20

    #pragma comment(linker, "/STACK:10240000,10240000")
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    using namespace std;
    const int N=300000+5,M=N*2,Inf=N*1000;
    void read(int &x){
        x=0;
        char ch=getchar();
        while (!('0'<=ch&&ch<='9'))
            ch=getchar();
        while ('0'<=ch&&ch<='9'){
            x=x*10+ch-48;
            ch=getchar();
        }
    }
    struct Edge{
        int cnt,y[M],z[M],nxt[M],fst[N];
        void set(){
            cnt=0;
            memset(y,0,sizeof y);
            memset(z,0,sizeof z);
            memset(nxt,0,sizeof nxt);
            memset(fst,0,sizeof fst);
        }
        void add(int a,int b,int c){
            cnt++;
            y[cnt]=b,z[cnt]=c;
            nxt[cnt]=fst[a],fst[a]=cnt;
        }
    }e;
    int n,m;
    vector <int> Tree[N];
    int father[N],son[N],deep[N],dis[N],fadis[N],bh[N],bhtot;
    int Anst[N][20];//Ancestor
    struct Query{
        int x,y,LCA,cost;
    }q[N];
    int Nextsum[N];
    void Build_Tree(int prev,int rt){
        bh[++bhtot]=rt;
        Tree[rt].clear(),deep[rt]=deep[prev]+1,son[rt]=0,father[rt]=prev;
        for (int i=e.fst[rt];i;i=e.nxt[i])
            if (e.y[i]!=prev){
                son[rt]++,Tree[rt].push_back(e.y[i]),
                fadis[e.y[i]]=e.z[i],dis[e.y[i]]=dis[rt]+e.z[i];
                Build_Tree(rt,e.y[i]);
            }
    }
    void LCA_Prepare(){
        memset(Anst,0,sizeof Anst);
        for (int i=1;i<=n;i++){
            int rt=bh[i];
            Anst[rt][0]=father[rt];
            for (int i=1;(1<<i)<=deep[rt];i++)
                Anst[rt][i]=Anst[Anst[rt][i-1]][i-1];
        }
    }
    int LCA(int a,int b){
        if (deep[a]>deep[b])
            swap(a,b);
        for (int i=deep[b]-deep[a],j=0;i>0;i>>=1,j++)
            if (i&1)
                b=Anst[b][j];
        if (a==b)
            return a;
        int k;
        for (k=0;(1<<k)<=deep[a];k++);
        for (;k>=0;k--)
            if ((1<<k)<=deep[a]&&Anst[a][k]!=Anst[b][k])
                a=Anst[a][k],b=Anst[b][k];
        return Anst[a][0];
    }
    bool check(int t){
        int total=0,Maxcost=0,Maxcut=0;
        memset(Nextsum,0,sizeof Nextsum);
        for (int i=1;i<=m;i++)
            if (q[i].cost>t){
                Maxcost=max(Maxcost,q[i].cost-t);
                total++;
                Nextsum[q[i].x]++;
                Nextsum[q[i].y]++;
                Nextsum[q[i].LCA]-=2;
            }
        for (int i=n;i>=1;i--)
            Nextsum[father[bh[i]]]+=Nextsum[bh[i]];
        for (int i=1;i<=n;i++)
            if (Nextsum[i]==total)
                Maxcut=max(Maxcut,fadis[i]);
        return Maxcost<=Maxcut;
    }
    int main(){
        scanf("%d%d",&n,&m);
        e.set();
        for (int i=1;i<n;i++){
            int a,b,c;
            read(a),read(b),read(c);
            e.add(a,b,c);
            e.add(b,a,c);
        }
        bhtot=0;
        deep[0]=-1,dis[1]=fadis[1]=0;
        Build_Tree(0,1);
        LCA_Prepare();
        for (int i=1;i<=m;i++){
            read(q[i].x),read(q[i].y);
            q[i].LCA=LCA(q[i].x,q[i].y);
            q[i].cost=dis[q[i].x]+dis[q[i].y]-dis[q[i].LCA]*2;
        }
        int le=0,ri=Inf,mid,ans=0;
        while (le<=ri){
            mid=(le+ri)>>1;
            if (check(mid))
                ri=mid-1,ans=mid;
            else
                le=mid+1;
        }
        printf("%d",ans);
        return 0;
    }
    
  • 1
    @ 2016-10-25 23:36:07

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int MAXN = 300000 + 10;

    int read(){
    char c = getchar();
    int x = 0;
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x*10 + c - '0', c = getchar();
    return x;
    }

    struct Edge{
    int to, w;
    Edge* p;
    Edge(int a=0, int b=0):to(a), w(b){}
    }map[MAXN], bri[MAXN * 3];

    int cnt = 0;
    void add(int a, int b, int c){
    Edge& now = bri[++cnt];
    now.to = b;
    now.w = c;
    now.p = map[a].p;
    map[a].p = &now;
    }

    int n, m, maxd;
    int dep[MAXN], f[MAXN][21], u[MAXN], v[MAXN], lca[MAXN], dist[MAXN], dis[MAXN], we[MAXN], sum[MAXN];

    int dfs(int x, int fa, int deep){
    dep[x] = deep;
    for(Edge* i = map[x].p; i != NULL; i = i->p){
    if(i->to == fa) continue;
    we[i->to] = i->w;
    f[i->to][0] = x;
    dist[i->to] = dist[x] + i->w;
    dfs(i->to, x, deep + 1);
    }
    }

    int LCA(int a, int b){
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 19; i >= 0; i--)
    if(f[a][i] && dep[f[a][i]] >= dep[b])
    a = f[a][i];
    if(a == b) return a;
    for(int i = 19; i >= 0; i--)
    if(f[a][i] != f[b][i])
    a = f[a][i], b = f[b][i];
    return f[a][0];
    }

    int maxe;

    void dfs2(int x, int father, int tot){
    for(Edge* i = map[x].p; i != NULL; i = i->p){
    if(i->to == father) continue;
    dfs2(i->to, x, tot);
    sum[x] += sum[i->to];
    }
    if(tot == sum[x]) maxe = max(maxe, we[x]);
    }

    bool check(int mid){
    int tot = 0;
    maxe = 0;
    for(int i = 1; i <= n; i++) sum[i] = 0;
    for(int i = 1; i <= m; i++)//查分优化!
    if(dis[i] > mid){
    sum[u[i]]++;
    sum[v[i]]++;
    sum[lca[i]] -= 2;
    tot++;
    }
    dfs2(1, -1, tot);
    if(maxd - maxe <= mid) return 1;
    return 0;
    }

    int main()
    {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) map[i].p = NULL;
    int l = 0, r = 0;
    for(int i = 1; i < n; i++){
    int a = read(), b = read(), c = read();
    add(a, b, c);
    add(b, a, c);
    }
    dfs(1, -1, 1);
    for(int j = 1; j < 19; j++)
    for(int i = 1; i <= n; i++)
    f[i][j] = f[f[i][j-1]][j-1];
    for(int i = 1; i <= m; i++){
    u[i] = read(), v[i] = read();
    lca[i] = LCA(u[i], v[i]);
    dis[i] = dist[u[i]] + dist[v[i]] - 2*dist[lca[i]];
    r = max(dis[i], r);
    }
    maxd = r;
    while(l < r){
    int mid = (l + r) >> 1;
    if(check(mid))
    r = mid;
    else
    l = mid + 1;
    }
    printf("%d", l);
    return 0;
    }
    LCA +查分+二分

  • 1
    @ 2016-10-08 14:24:41

    二分答案+链剖求lca+树上的差分序列

    #include<cstdio>
    #include<cstring>
    #include<cctype>
    #include<algorithm>
    using namespace std;
    #define rep(i,s,t) for(int i=s;i<=t;i++)
    #define dwn(i,s,t) for(int i=s;i>=t;i--)
    #define clr(x,c) memset(x,c,sizeof(x))
    #define qwq(x) for(edge *o=head[x];o;o=o->next)
    #define lson l,mid,x<<1
    #define rson mid+1,r,x<<1|1
    int read(){
    int x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x;
    }
    const int nmax=3e5+5;
    const int inf=0x7f7f7f7f;
    struct edge{
    int to,dist;edge *next;
    };
    edge es[nmax<<1],*pt=es,*head[nmax];
    struct node{
    int u,v,lca,dist;
    bool operator<(const node&rhs)const{
    return dist>rhs.dist;}
    };node ns[nmax];
    void add(int u,int v,int d){
    pt->to=v;pt->dist=d;pt->next=head[u];head[u]=pt++;
    pt->to=u;pt->dist=d;pt->next=head[v];head[v]=pt++;
    }
    int fa[nmax],dep[nmax],tp[nmax],id[nmax],idx[nmax],son[nmax],sz[nmax],n,m,dist[nmax],num[nmax],w[nmax];
    void dfs(int x,int ta){
    sz[x]=1;
    qwq(x) if(o->to!=ta){
    dep[o->to]=dep[x]+1;fa[o->to]=x;w[o->to]=o->dist;dist[o->to]=dist[x]+o->dist;
    dfs(o->to,x);sz[x]+=sz[o->to];
    if(sz[o->to]>sz[son[x]]||!son[x]) son[x]=o->to;
    }
    }
    void DFS(int x,int top){
    tp[x]=top;id[++id[0]]=x;idx[x]=id[0];
    if(son[x]) DFS(son[x],top);
    qwq(x) if(!idx[o->to]) DFS(o->to,o->to);
    }
    void query(int a,int b,int cur){
    ns[cur].dist=dist[a]+dist[b];
    while(tp[a]!=tp[b]){
    if(dep[tp[a]]>dep[tp[b]]) swap(a,b);
    b=fa[tp[b]];
    }
    if(dep[a]>dep[b]) swap(a,b);
    ns[cur].dist-=dist[a]*2;ns[cur].lca=a;
    return ;
    }
    void get_cnt(int x,int fa){
    qwq(x) if(o->to!=fa){
    get_cnt(o->to,x);
    num[x]+=num[o->to];
    }
    }
    bool check(int x){
    int cnt=0;
    rep(i,1,m) if(ns[i].dist>x) ++cnt;else break;
    if(!cnt) return 1;
    clr(num,0);
    rep(i,1,cnt) num[ns[i].u]++,num[ns[i].v]++,num[ns[i].lca]-=2;
    get_cnt(1,0);
    int tmax=0;
    rep(i,1,n) if(num[i]==cnt) tmax=max(tmax,w[i]);
    return ns[1].dist-tmax<=x;
    }
    int main(){
    n=read(),m=read();int u,v,d,tm=0;
    rep(i,1,n-1) u=read(),v=read(),d=read(),add(u,v,d),tm+=d;
    dfs(1,0);DFS(1,1);
    //rep(i,1,n) printf("%d %d %d %d %d %d %d %d\n",dep[i],fa[i],son[i],sz[i],tp[i],id[i],idx[i],w[i]);
    rep(i,1,m) ns[i].u=read(),ns[i].v=read(),query(ns[i].u,ns[i].v,i);
    sort(ns+1,ns+m+1);
    //rep(i,1,m) printf("%d %d\n",ns[i].lca,ns[i].dist);
    int l=1,r=tm,mid,ans=0;
    while(l<=r){
    mid=(l+r)>>1;
    if(check(mid)) ans=mid,r=mid-1;
    else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
    }

  • 1
    @ 2016-09-05 19:27:27

    //noip 2015 day2 t3
    //rt http://www.cnblogs.com/yanlifneg/p/5559491.html
    // 二分答案

    {
    倍增求出路径长度

    判断: 判断有多少条路径>mid t 同时求出最大差值
    对于每一个点求不合法的路径求经过它的次数,如果 =t
    且如果它的父边>=差值 则 删去 exit(true)

    判断次数(sum[i]+1, sum[j]+1, sum[lca(i,j)]-2) 查分
    然后遍历加和。
    O(nlogn)

    ( 常数很大,因此第20个点是卡着过的,, 在其他oj都tle,, 而且,中间我调试时又一次错误非常明显,结果还是95.。。 )

    }

    
    uses math;
    type
        re=record
            v,len,next:longint;
        end;
        rea=record
            u,v:longint;
            len:longint;
        end;
    var
        n,m,u,v,z,tot,i,j,max_deep,l,r,mid,max_cz:longint;
        last,dis_head,deep,sum,father,f_b:array[0..300000]of longint;
        lj:array[0..300000]of rea;
        f:array[0..300000,0..20]of longint;
        t:array[0..300000*2]of re;
    
    procedure add(u,v,z:longint);
    begin
        inc(tot);
        t[tot].v:=v;
        t[tot].len:=z;
        t[tot].next:=last[u];
        last[u]:=tot;
    end;
    
    procedure In_Dfs(i,fat:longint);
    var
        x,tox:longint;
    begin
        x:=last[i];
        while x<>0 do
        begin
            tox:=t[x].v;
            if tox<>fat then
            begin
                deep[tox]:=deep[i]+1;
                father[tox]:=i;
                f_b[tox]:=x;
                dis_head[tox]:=dis_head[i]+t[x].len;
                max_deep:=max(max_deep,deep[tox]);
                f[tox][0]:=i;
                In_Dfs(tox,i);
            end;
            x:=t[x].next;
        end;
    end;
    
    procedure Init_f;
    var
        i,j:longint;
    begin
        for j:=1 to trunc(ln(max_deep)/ln(2)) do
            for i:=1 to n do
                if 1<<j<=deep[i] then f[i][j]:=f[f[i][j-1]][j-1];
    end;
    
    procedure swap(var x,y:longint);
    var
        tmp:longint;
    begin
        tmp:=x; x:=y; y:=tmp;
    end;
    
    function lca(x,y:longint):longint;
    var
        p,k:longint;
    begin
        if deep[x]<deep[y] then swap(x,y);
        p:=deep[x]-deep[y];
        k:=0;
        while p<>0 do
        begin
            if (p and 1=1) then x:=f[x][k];
            inc(k);
            p:=p>>1;
        end;
            if x=y then exit(x);
        k:=0;
        while k>=0 do
        begin
            if f[x][k]<>f[y][k] then
            begin
                x:=f[x][k];
                y:=f[y][k];
                inc(k);
            end else dec(k);
        end;
            exit(f[x][0]);
    end;
    
    procedure Init_lj;
    var
        i:longint;
    begin
        for i:=1 to m do
        begin
            readln(lj[i].u,lj[i].v);
            lj[i].len:=(dis_head[lj[i].u]+dis_head[lj[i].v]-2*dis_head[lca(lj[i].u,lj[i].v)]);
                    r:=max(r,lj[i].len);
        end;
    end;
    
    procedure Init;
    var
        i,j:longint;
    begin
        readln(n,m);
        for i:=1 to n-1 do
        begin
            readln(u,v,z);
            add(u,v,z);
            add(v,u,z);
        end;
        In_Dfs(1,0);
        Init_f;
        Init_lj;
    end;
    
    procedure Dfs_sum(i,fat:longint);
    var
        x,tox:longint;
    begin
        x:=last[i];
        while x<>0 do
        begin
            tox:=t[x].v;
            if tox<>fat then 
            begin
                Dfs_sum(tox,i);
                sum[i]:=sum[i]+sum[tox];
            end;
            x:=t[x].next;
        end;
    end;
    
    
    
    
    function check(mid:longint):boolean;
    var
        i,j,max_cz,tot,x,zx:longint;
    begin
        tot:=0; max_cz:=0;
        for i:=1 to n do sum[i]:=0;
        for i:=1 to m do
            if lj[i].len>mid then
            begin
                inc(tot);
                max_cz:=max(max_cz,lj[i].len-mid);
                inc(sum[lj[i].u]); inc(sum[lj[i].v]);
                zx:=lca(lj[i].u,lj[i].v);
                dec(sum[zx],2)
            end;
        Dfs_sum(1,0);
        for i:=1 to n do
            if (sum[i]=tot)and(t[f_b[i]].len>=max_cz) then exit(true);
        exit(false);
    end;
    
    begin
        Init;
        while l<>r do
        begin
            mid:=(l+r)>>1;
            if check(mid) then r:=mid else
                l:=mid+1;
        end;
        writeln(l);
    end.```
    
  • 1
    @ 2016-08-30 15:55:10

    同下,大牛程序看不懂系列
    ```c++
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <map>
    #include <stack>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <fstream>
    #include <time.h>
    #include <cctype>
    #include <vector>
    #include <set>
    #define pb push_back
    #define N 700100

    using namespace std;

    int dp,pre[N],p[N],tt[N],ww[N],fa[N],deep[N],v[N],A[N],B[N],LCA[N];

    int s[N][20],n,m,a,b,c,i,sum[N],ans,cnt,dis[N],dist[N];

    void link(int x,int y,int z)
    {
    dp++;
    pre[dp]=p[x];
    p[x]=dp;
    tt[dp]=y;
    ww[dp]=z;
    }

    void dfs(int x)
    {
    int i;
    i=p[x];
    while (i)
    {
    if (tt[i]!=fa[x])
    {
    deep[tt[i]]=deep[x]+1;
    fa[tt[i]]=x;
    v[tt[i]]=ww[i];
    dis[tt[i]]=dis[x]+ww[i];
    dfs(tt[i]);
    }
    i=pre[i];
    }
    }

    int lca(int x,int y)
    {
    if(deep[x]>deep[y])x^=y^=x^=y;
    int i;
    for(i=19;i>=0;i--)
    {
    if(deep[y]-deep[x]>=(1<<i))
    {
    y=s[y][i];
    }
    }
    if(x==y)return x;
    for(i=19;i>=0;i--)
    {
    if(s[x][i]!=s[y][i])
    {
    x=s[x][i];
    y=s[y][i];
    }
    }
    return fa[x];
    }

    void gao(int x)
    {
    int i=p[x];
    while (i)
    {
    if (tt[i]!=fa[x])
    {
    gao(tt[i]);
    sum[x]+=sum[tt[i]];
    }
    i=pre[i];
    }
    }

    int check(int x)
    {
    int cnt=0,dec=0;
    for (i=1;i<=n;i++)
    sum[i]=0;
    for (i=1;i<=m;i++)
    if (dist[i]>x)
    {
    cnt++;
    dec=max(dec,dist[i]-x);
    sum[A[i]]++;
    sum[B[i]]++;
    sum[LCA[i]]-=2;
    }
    gao(1);
    for (i=1;i<=n;i++)
    if ((sum[i]==cnt)&&(v[i]>=dec)) return 1;
    return 0;
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for (i=1;i<n;i++)
    {
    scanf("%d%d%d",&a,&b,&c);
    link(a,b,c);
    link(b,a,c);
    }
    dfs(1);
    for(i=1;i<=n;i++)s[i][0]=fa[i];
    for(int h=1;h<20;h++)
    {
    for(i=1;i<=n;i++)
    {
    s[i][h]=s[s[i][h-1]][h-1];
    }
    }
    for (i=1;i<=m;i++)
    {
    scanf("%d%d",&A[i],&B[i]);
    LCA[i]=lca(A[i],B[i]);
    dist[i]=dis[A[i]]+dis[B[i]]-2*dis[LCA[i]];
    }
    int L=0,R=0;
    for (i=1;i<=m;i++)
    R=max(R,dist[i]);
    int mid;
    while (L<=R)
    {
    mid=(L+R)>>1;
    if (check(mid))
    R=mid-1;
    else
    L=mid+1;
    }
    printf("%d\n",L);
    return 0;
    }
    ```

    • @ 2016-10-28 20:44:57

      太感谢了!!!易懂!!!模模模!!!

  • 1
    @ 2016-08-14 14:45:34

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 80400 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 80400 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 80400 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 80396 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 80420 KiB, score = 5
    测试数据 #5: Accepted, time = 15 ms, mem = 80448 KiB, score = 5
    测试数据 #6: Accepted, time = 15 ms, mem = 80484 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 80396 KiB, score = 5
    测试数据 #8: Accepted, time = 0 ms, mem = 80400 KiB, score = 5
    测试数据 #9: Accepted, time = 15 ms, mem = 80396 KiB, score = 5
    测试数据 #10: Accepted, time = 109 ms, mem = 80552 KiB, score = 5
    测试数据 #11: Accepted, time = 171 ms, mem = 80592 KiB, score = 5
    测试数据 #12: RuntimeError, time = 78 ms, mem = 82420 KiB, score = 0
    测试数据 #13: RuntimeError, time = 93 ms, mem = 82416 KiB, score = 0
    测试数据 #14: RuntimeError, time = 78 ms, mem = 82416 KiB, score = 0
    测试数据 #15: RuntimeError, time = 109 ms, mem = 82416 KiB, score = 0
    测试数据 #16: Accepted, time = 265 ms, mem = 80548 KiB, score = 5
    测试数据 #17: Accepted, time = 265 ms, mem = 80572 KiB, score = 5
    测试数据 #18: Accepted, time = 312 ms, mem = 80584 KiB, score = 5
    测试数据 #19: TimeLimitExceeded, time = 1125 ms, mem = 80988 KiB, score = 0
    TimeLimitExceeded, time = 2665 ms, mem = 82420 KiB, score = 75
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #define LL long long
    #define inf 1000000000
    using namespace std;
    const int N=300000+5;
    const int M=300000+5;
    struct edge
    {
    int v,w;
    edge *next;
    }E[M*2],*p=E,*point[N*2];
    struct node
    {
    int a1,b1,anc,dis;
    }lca[N*2];
    inline void add(int x,int y,int z)
    {
    p++; p->v=y; p->w=z; p->next=point[x];
    point[x]=p;
    }
    int anc[N][31],fa[N],dep[N],dis[N],sum[N];
    void dfs(int x)
    {
    anc[x][0]=fa[x];
    for (int i=1; i<=30; i++)
    anc[x][i]=anc[anc[x][i-1]][i-1];
    for (edge *j=point[x]; j; j=j->next)
    if (j->v!=fa[x])
    {
    fa[j->v]=x;
    dep[j->v]=dep[x]+1;
    dis[j->v]=dis[x]+j->w;
    dfs(j->v);
    }
    }
    int LCA(int x,int y)
    {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=30; i>=0; i--)
    if (dep[y]<=dep[anc[x][i]]) x=anc[x][i];
    if (x==y) return x;
    for (int i=30; i>=0; i--)
    if (anc[x][i]!=anc[y][i])
    {
    x=anc[x][i];
    y=anc[y][i];
    }
    return anc[x][0];
    }
    void get_sum(int x)
    {
    for (edge *j=point[x]; j; j=j->next)
    if (j->v!=fa[x])
    {
    get_sum(j->v);
    sum[x]+=sum[j->v];
    }
    }
    int n,m,l=0,r=0,mid;
    bool check(int limit)
    {
    int tot=0, p=0;
    memset(sum,0,sizeof(sum));
    for (int i=1; i<=m; i++)
    if (lca[i].dis>limit)
    {
    tot++;
    sum[lca[i].a1]++;
    sum[lca[i].b1]++;
    sum[lca[i].anc]-=2;
    p=max(p,lca[i].dis-limit);
    }
    get_sum(1);
    for (int i=1; i<=n; i++)
    if (sum[i]==tot)
    for (edge *j=point[i]; j; j=j->next)
    if (j->v==fa[i]&&j->w>=p) return 1;
    return 0;
    }
    void solve()
    {
    scanf("%d%d",&n,&m);
    for (int i=1; i<n; i++)
    {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z); add(y,x,z);
    }
    dfs(1);
    for (int i=1; i<=m; i++)
    {
    scanf("%d%d",&lca[i].a1,&lca[i].b1);
    lca[i].anc=LCA(lca[i].a1,lca[i].b1);
    lca[i].dis=dis[lca[i].a1]+dis[lca[i].b1]-2*dis[lca[i].anc];
    r=max(r,lca[i].dis);
    }
    while (l<=r)
    {
    mid=(l+r)>>1;
    if (check(mid)) r=mid-1;
    else l=mid+1;
    }
    printf("%d\n",r+1);
    }
    int main()
    {
    solve();
    return 0;
    }
    求指教。。。。。。。。。为什么会运行时错误,运行时错误是smg。。。。。。

    • @ 2016-08-19 22:04:53

      Vijos似乎刚刚改大栈空间,试试重交一遍?

  • 1
    @ 2015-11-14 11:59:24

    ###大牛的程序我看不懂!!!

    记录信息
    评测状态 Accepted
    题目 P1983 运输计划
    递交时间 2015-11-14 11:19:34
    代码语言 C++
    评测机 VijosEx
    消耗时间 1605 ms
    消耗内存 44876 KiB
    评测时间 2015-11-14 11:19:39
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 44872 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 44872 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 44868 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 44876 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 44872 KiB, score = 5
    测试数据 #5: Accepted, time = 0 ms, mem = 44868 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 44872 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 44872 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 44868 KiB, score = 5
    测试数据 #9: Accepted, time = 15 ms, mem = 44872 KiB, score = 5
    测试数据 #10: Accepted, time = 46 ms, mem = 44872 KiB, score = 5
    测试数据 #11: Accepted, time = 78 ms, mem = 44872 KiB, score = 5
    测试数据 #12: Accepted, time = 109 ms, mem = 44876 KiB, score = 5
    测试数据 #13: Accepted, time = 125 ms, mem = 44872 KiB, score = 5
    测试数据 #14: Accepted, time = 125 ms, mem = 44868 KiB, score = 5
    测试数据 #15: Accepted, time = 140 ms, mem = 44872 KiB, score = 5
    测试数据 #16: Accepted, time = 109 ms, mem = 44872 KiB, score = 5
    测试数据 #17: Accepted, time = 125 ms, mem = 44872 KiB, score = 5
    测试数据 #18: Accepted, time = 156 ms, mem = 44872 KiB, score = 5
    测试数据 #19: Accepted, time = 562 ms, mem = 44872 KiB, score = 5
    Accepted, time = 1605 ms, mem = 44876 KiB, score = 100
    代码
    #include<algorithm>
    #include <iostream>
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    #include <vector>
    #include <queue>
    #include <map>
    #include <set>
    using namespace std;

    const int N=300005;

    #define next _Next

    struct Route
    {
    int u,v,l;
    }R[N];

    inline bool operator<(const Route& A,const Route& B)
    {
    return A.l>B.l;
    }

    int n,m,e[N<<1],L[N<<1],next[N<<1],G[N],tot,dep[N],fa[N][20],dst[N],Rou[N],Rtot,RouL[N],Mark[N],Max[N];

    void adde(int u,int v,int l)
    {
    e[++tot]=v;next[tot]=G[u];G[u]=tot;L[tot]=l;
    e[++tot]=u;next[tot]=G[v];G[v]=tot;L[tot]=l;
    }

    void bfs()
    {
    static int q[N]={},a=1,b=1;
    q[1]=1;dep[1]=1;
    while(a<=b)
    {
    int u=q[a++];
    for(int i=0;fa[fa[u][i]][i];i++)
    fa[u][i+1]=fa[fa[u][i]][i];
    for(int i=G[u];i;i=next[i])
    if(!dep[e[i]])
    dep[e[i]]=dep[u]+1,dst[e[i]]=dst[u]+L[i],fa[e[i]][0]=u,q[++b]=e[i];
    }
    }

    inline int Lca(int u,int v)
    {
    if(dep[u]<dep[v])
    swap(u,v);
    for(int i=19;~i;i--)
    if(dep[fa[u][i]]>=dep[v])
    u=fa[u][i];
    if(u==v)
    return u;
    for(int i=19;~i;i--)
    if(fa[u][i]!=fa[v][i])
    u=fa[u][i],v=fa[v][i];
    return fa[u][0];
    }

    inline int dis(int u,int v)
    {
    return dst[u]+dst[v]-2*dst[Lca(u,v)];
    }

    void get_rou(int u,int v)
    {
    int lca=Lca(u,v);
    Rtot=dep[u]+dep[v]-2*dep[lca]+1;
    int Now=0;
    while(u!=lca)
    {
    Rou[++Now]=u;RouL[Now]=dst[u]-dst[fa[u][0]];u=fa[u][0];
    }
    Now=Rtot;
    Rou[Now]=v;
    while(v!=lca)
    {
    u=v;v=fa[u][0];Rou[--Now]=v;RouL[Now]=dst[u]-dst[v];
    }
    }

    void mark_all()
    {
    int q[N]={},a=1,b=0;
    for(int i=1;i<=Rtot;i++)
    Mark[Rou[i]]=i,q[++b]=Rou[i];
    while(a<=b)
    {
    int u=q[a++];
    for(int i=G[u];i;i=next[i])
    if(!Mark[e[i]])
    Mark[e[i]]=Mark[u],q[++b]=e[i];
    }
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,l;i<n;i++)
    scanf("%d%d%d",&u,&v,&l),adde(u,v,l);
    bfs();
    for(int i=1;i<=m;i++)
    scanf("%d%d",&R[i].u,&R[i].v),R[i].l=dis(R[i].u,R[i].v);
    sort(R+1,R+m+1);
    if(R[1].l==0)
    {
    cout<<0<<endl;return 0;
    }
    get_rou(R[1].u,R[1].v);
    mark_all();
    int Lnow=1,Rnow=Rtot;
    for(int i=1;i<=m;i++)
    {
    int Le=Mark[R[i].u],Ri=Mark[R[i].v];
    if(Le>Ri)
    swap(Le,Ri);
    if(Lnow<Le)
    {
    for(int j=Lnow;j<Rnow&&j<Le;j++)
    Max[j]=R[i].l;
    Lnow=Le;
    }
    if(Ri<Rnow)
    {
    for(int j=max(Lnow,Ri);j<Rnow;j++)
    Max[j]=R[i].l;
    Rnow=Ri;
    }
    if(Lnow>=Rnow)
    break;
    }
    int Ans=R[1].l;
    for(int i=1;i<Rtot;i++)
    Ans=min(Ans,max(R[1].l-RouL[i],Max[i]));
    cout<<Ans<<endl;
    return 0;
    }
    ###我的60‘
    记录信息
    评测状态 Time Limit Exceeded
    题目 P1983 运输计划
    递交时间 2015-11-14 11:36:33
    代码语言 C++
    评测机 VijosEx
    消耗时间 4476 ms
    消耗内存 23424 KiB
    评测时间 2015-11-14 11:36:39
    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:76:24: warning: unknown conversion type character 'l' in format [-Wformat=]
    printf("%lld\n",ans);
    ^
    foo.cpp:76:24: warning: too many arguments for format [-Wformat-extra-args]
    foo.cpp:61:13: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int pre,now;
    ^
    测试数据 #0: Accepted, time = 0 ms, mem = 21408 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 21408 KiB, score = 5
    测试数据 #2: Accepted, time = 15 ms, mem = 21408 KiB, score = 5
    测试数据 #3: Accepted, time = 0 ms, mem = 21412 KiB, score = 5
    测试数据 #4: Accepted, time = 0 ms, mem = 21444 KiB, score = 5
    测试数据 #5: Accepted, time = 31 ms, mem = 21492 KiB, score = 5
    测试数据 #6: Accepted, time = 78 ms, mem = 21544 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 21412 KiB, score = 5
    测试数据 #8: Accepted, time = 0 ms, mem = 21412 KiB, score = 5
    测试数据 #9: Accepted, time = 15 ms, mem = 21412 KiB, score = 5
    测试数据 #10: Accepted, time = 46 ms, mem = 21644 KiB, score = 5
    测试数据 #11: Accepted, time = 62 ms, mem = 21700 KiB, score = 5
    测试数据 #12: RuntimeError, time = 46 ms, mem = 23420 KiB, score = 0
    测试数据 #13: RuntimeError, time = 46 ms, mem = 23424 KiB, score = 0
    测试数据 #14: RuntimeError, time = 31 ms, mem = 23424 KiB, score = 0
    测试数据 #15: RuntimeError, time = 46 ms, mem = 23420 KiB, score = 0
    测试数据 #16: TimeLimitExceeded, time = 1015 ms, mem = 21628 KiB, score = 0
    测试数据 #17: TimeLimitExceeded, time = 1015 ms, mem = 21652 KiB, score = 0
    测试数据 #18: TimeLimitExceeded, time = 1015 ms, mem = 21692 KiB, score = 0
    测试数据 #19: TimeLimitExceeded, time = 1015 ms, mem = 22292 KiB, score = 0
    TimeLimitExceeded, time = 4476 ms, mem = 23424 KiB, score = 60
    代码
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int nxt[600123],fir[300123],fa[300123][2],val[600123],t[600123],dep[300123],cnt;
    long long to[600123];
    int n,m;
    long long mem[2][300123];
    long long ans;
    void sw(int &a,int &b)
    {
    a=a^b;
    b=a^b;
    a=a^b;
    }
    void add(int a,int b,int v)
    {
    nxt[++cnt]=fir[a];
    val[cnt]=v;
    to[cnt]=b;
    fir[a]=cnt;
    }
    void search(int node,int pre)
    { dep[node]=dep[pre]+1;
    for(int i=fir[node];i;i=nxt[i])
    { if(to[i]==pre)continue;
    fa[to[i]][0]=node;
    fa[to[i]][1]=i;
    search(to[i],node);
    }
    }
    long long DO_IT(int x,int y,int k)
    {
    long long tot=0;
    if(dep[x]<dep[y])sw(x,y);
    while(dep[x]>dep[y]){
    t[fa[x][1]]=k;
    tot+=val[fa[x][1]];
    x=fa[x][0];
    }
    while(x!=y){
    t[fa[x][1]]=k;
    tot+=val[fa[x][1]];
    t[fa[y][1]]=k;
    tot+=val[fa[y][1]];
    x=fa[x][0];
    y=fa[y][0];
    }
    return tot;
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    add(a,b,c);
    add(b,a,c);
    }
    search(1,1);
    int pre,now;
    for(int i=1;m--;i++)
    { pre=(i+1)%2;
    now=i%2;
    int a,b;
    scanf("%d%d",&a,&b);
    long long tot=DO_IT(a,b,i+2*m+1);
    for(int j=1;j<=cnt;j++)
    { int ss=(t[j]==i+2*m+1)?val[j]:0;
    mem[now][j]=max(mem[pre][j],tot-ss);
    }
    }
    ans=2333333333;
    for(int i=1;i<=cnt;i++)
    ans=min(ans,mem[now][i]);
    printf("%lld\n",ans);

    return 0;
    }

  • 1
    @ 2015-11-10 21:48:36

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 6536 KiB, score = 5

    测试数据 #1: Accepted, time = 0 ms, mem = 6532 KiB, score = 5

    测试数据 #2: WrongAnswer, time = 0 ms, mem = 6532 KiB, score = 0

    测试数据 #3: Accepted, time = 15 ms, mem = 6536 KiB, score = 5

    测试数据 #4: Accepted, time = 15 ms, mem = 6588 KiB, score = 5

    测试数据 #5: Accepted, time = 46 ms, mem = 6644 KiB, score = 5

    测试数据 #6: Accepted, time = 78 ms, mem = 6708 KiB, score = 5

    测试数据 #7: Accepted, time = 15 ms, mem = 6532 KiB, score = 5

    测试数据 #8: Accepted, time = 0 ms, mem = 6536 KiB, score = 5

    测试数据 #9: Accepted, time = 15 ms, mem = 6536 KiB, score = 5

    测试数据 #10: Accepted, time = 671 ms, mem = 6760 KiB, score = 5

    测试数据 #11: Accepted, time = 1000 ms, mem = 6808 KiB, score = 5

    测试数据 #12: TimeLimitExceeded, time = 1015 ms, mem = 6532 KiB, score = 0

    测试数据 #13: TimeLimitExceeded, time = 1015 ms, mem = 6532 KiB, score = 0

    测试数据 #14: TimeLimitExceeded, time = 1015 ms, mem = 6536 KiB, score = 0

    测试数据 #15: TimeLimitExceeded, time = 1015 ms, mem = 6536 KiB, score = 0

    测试数据 #16: TimeLimitExceeded, time = 1015 ms, mem = 6828 KiB, score = 0

    测试数据 #17: TimeLimitExceeded, time = 1015 ms, mem = 6864 KiB, score = 0

    测试数据 #18: TimeLimitExceeded, time = 1015 ms, mem = 6532 KiB, score = 0

    测试数据 #19: RuntimeError, time = 46 ms, mem = 6536 KiB, score = 0

    TimeLimitExceeded, time = 9006 ms, mem = 6864 KiB, score = 55

    首先声明,这个程序是
    乱搞的!
    乱搞的!
    乱搞的!
    考场上正解写不出来。。。毕竟蒟蒻一个,连LCA都不会。。然而居然骗这么多分,我感觉到爽翻了。。。
    做法:贪心:对于每个计划DFS一遍,找到计划中最大边删掉,如果此时的距离最大,更新MAXDIS,最后输出MAXDIS

    顺便说一下,样例2都没过。。。
    ###Block Code
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    using namespace std;
    int u[200001],v[200001],w[200001],first[200001],cnt[200001],pu[200001],pv[200001],t;
    int dis[200001],maxdis=0,maxdisn=0;
    void quicksort(int left,int right) {
    if (left>=right) return;
    int i=left,j=right,t=0;
    while (i<j) {
    while (i<j && u[left]<=u[j]) j--;
    while (i<j && u[i]<=u[left]) i++;
    if (i<j) {
    t=w[i];
    w[i]=w[j];
    w[j]=t;
    t=u[i];
    u[i]=u[j];
    u[j]=t;
    t=v[i];
    v[i]=v[j];
    v[j]=t;
    }
    }
    t=w[left];
    w[left]=w[i];
    w[i]=t;
    t=u[left];
    u[left]=u[i];
    u[i]=t;
    t=v[left];
    v[left]=v[i];
    v[i]=t;
    quicksort(left,i-1);
    quicksort(i+1,right);
    return;
    }
    int dfs(int x,int mubiao,int maxnow) {
    int target=first[x]+cnt[x];
    int nowcost=dis[x];
    for (int i=first[x];i<target;i++) {
    if (dis[v[i]]==-1) {
    dis[v[i]]=nowcost+w[i];
    if (v[i]==mubiao) {
    return max(maxnow,w[i]);
    }
    int re=dfs(v[i],mubiao,max(maxnow,w[i]));
    if (re!=0) return re;
    }
    }
    return 0;
    }
    int main() {
    int n,m;
    // freopen("transport.in","r",stdin);
    // freopen("transport.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++) {
    int j=i<<1;
    int a,b,r;
    scanf("%d%d%d",&a,&b,&r);
    u[j-1]=a;
    v[j-1]=b;
    w[j-1]=r;
    v[j]=a;
    u[j]=b;
    w[j]=r;
    cnt[a]++;
    cnt[b]++;
    }
    t=(n-1)<<1;
    quicksort(1,t);
    int now=-1;
    for (int i=1;i<=t;i++) {
    if (u[i]!=now) {
    now=u[i];
    first[now]=i;
    }
    }
    // printf("read & sort complete!");
    if (m*n>1000000) m=10000;
    for (int i=1;i<=m;i++) {
    scanf("%d%d",&pu[i],&pv[i]);
    for (int j=1;j<=n;j++)
    dis[j]=-1;
    dis[pu[i]]=0;
    int maxnow=dfs(pu[i],pv[i],0);
    // printf("%d->%d:%d",pu[i],pv[i],dis[pv[i]]);
    if (maxdis<dis[pv[i]]-maxnow) {
    maxdis=dis[pv[i]]-maxnow;
    }
    }
    printf("%d",maxdis);
    return 0;
    }

    • @ 2015-11-11 09:17:32

      666,我也是这么写的。

    • @ 2015-11-11 12:08:34

      Jump ;)

    • @ 2016-11-05 11:01:19

      思路一样,不知道Pascal这样能不能过

  • 0
    @ 2017-04-06 11:42:42

    其实2个dfs就完了的说
    。。。。

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    //AC
    
    const int maxn=2*300000+50;
    const int maxm=2*300000+50;
    const int max_log_n=20;
    inline int read()
    {
        char c;int x=1,res=0;
        c=getchar();
        while(!isdigit(c))
        {
            if(c=='-') x=-1;
            c=getchar();
        }
        while(isdigit(c))
        {
            res=res*10+c-'0';
            c=getchar();
        }
        return res*x;
    }
    int rnk[maxn];///////////////
    int sz=0;
    int head[maxn];
    struct edge
    {
        int to,cost,next;
    };
    edge es[maxn];
    int cnt=0;
    void addedge(int from,int to,int cost)
    {
        es[++cnt].to=to;es[cnt].next=head[from];es[cnt].cost=cost;head[from]=cnt;
    }
    int pa[max_log_n][maxn];
    int n,m;
    int depth[maxn];
    int dis[maxn];
    struct plan{int id,from,to,cost,anse;};
    plan ps[maxm];
    int maxcost=-1;
    vector<int > tar;
    int add[maxn];
    int sum[maxn];//子树标记之和
    int prevc[maxn];
    void dfs(int v,int fa)
    {
        depth[v]=depth[fa]+1;
        pa[0][v]=fa;
        int k=1;
        if(pa[k-1][v]!=0)
        {
            while(pa[k-1][pa[k-1][v]]!=0)
            {
                pa[k][v]=pa[k-1][pa[k-1][v]];
                k++;
            }
        }
        for(int i=head[v];i>0;i=es[i].next)
        {
            edge &e=es[i];
            if(e.to!=fa)
            {
                dis[e.to]=dis[v]+e.cost;
                prevc[e.to]=e.cost;
                dfs(e.to,v);
            }
        }
        rnk[++sz]=v;
    }
    
    
    int lca(int u,int v)
    {
        if(depth[u]>depth[v])
        {
            swap(u,v);
        }
        for(int k=max_log_n-1;k>=0;k--)
        {
            if(depth[v]-depth[u]>>k&1)
            {
                v=pa[k][v];
            }
        }
        if(v==u) return u;
        else
        {
            for(int k=max_log_n-1;k>=0;k--)
            {
                if(pa[k][u]!=pa[k][v])
                {
                    u=pa[k][u];v=pa[k][v];
                }
            }
            return pa[0][u];
        }
    }
    
    void dfs2(int v,int fa)
    {
        sum[v]=add[v];
        for(int j=head[v];j>0;j=es[j].next)
        {
            edge &e=es[j];
            if(e.to!=fa)
            {
                dfs2(e.to,v);
                sum[v]+=sum[e.to];
            }
        }
    }
    
    bool cal(int x,bool debug=false)
    {
        /*/
        if(x==70)
        {
            debug=true;
        }
        /*/
        tar.clear();
        for(int i=1;i<=m;i++)
        {
            if(ps[i].cost>x)
            {
                tar.push_back(i);
            }
        }
        int maxx=-1;
        memset(add,0,sizeof(add));
        memset(sum,0,sizeof(sum));
        for(unsigned j=0;j<tar.size();j++)
        {
            int num=tar[j];
            int v=ps[num].from;int u=ps[num].to;
            add[v]+=1;
            add[u]+=1;
            add[ps[num].anse]-=2;
            maxx=max(ps[num].cost-x,maxx);
        }
        dfs2(1,0);
        /*
        for(int i=1,u;i<=n;i++)
        {
            u=rnk[i];
            add[pa[0][u]]+=add[u];
        }
        */
        if(debug)
        {
            printf("sum:\n");
            for(int i=1;i<=n;i++)
            {
                printf("sum[%d]=%d\n",i,sum[i]);
            }
            printf("\n");
            for(int i=1;i<=n;i++)
            {
                printf("sum[%d]=%d\n",i,sum[i]);
            }
            printf("maxdel=%d\n",maxx);
            printf("\n");
            printf("total=%d\n",tar.size());
            printf("prevc:\n");
            for(int i=1;i<=n;i++)
            {
                printf("%d\n",prevc[i]);
            }
            printf("\n");
        }
        int dec=-1;
        for(int i=1;i<=n;i++)
        {
            if(sum[i]==(int)tar.size())
            {
                //i为要删除的边的下点
                if(prevc[i]>=maxx)
                {
                    dec=max(dec,prevc[i]);
                }
            }
        }
        return dec>=maxx;
    }
    
    inline int solve()
    {
        /*
        for(int i=1;i<=sz;i++)
        {
            printf("rnk[%d]=%d\n",i,rnk[i]);
        }
        printf("\n");
        */
        for(int i=1;i<=m;i++)
        {
            int u=ps[i].from;
            int v=ps[i].to;
            if(depth[u]>depth[v]) swap(u,v);
            ps[i].anse=lca(u,v);int zu=ps[i].anse;
            ps[i].cost=dis[u]+dis[v]-2*dis[zu];
            maxcost=max(maxcost,ps[i].cost);
        }
        int l=-1;int r=3*100000000;
        while(l<r-1)
        {
            int mid=l+(r-l)/2;
            //printf("%d\n",mid);
            if(cal(mid))
            {
                r=mid;
            }
            else l=mid;
        }
        return r;
    }
    
    int main()
    {
        /*
        #ifdef ONLINE_JUDGE
            freopen("1.out","w",stdout);
        #endif
        */
        //freopen("WA.out","w",stdout);
        n=read();m=read();
        for(int i=0;i<n-1;i++)
        {
            int from,to,cost;
            from=read();to=read();cost=read();
            addedge(from,to,cost);
            addedge(to,from,cost);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            ps[i].from=read();ps[i].to=read();
        }
        printf("%d\n",solve());
        return 0;
    }
    
  • 0
    @ 2016-10-21 12:24:58

    看到题解中一堆大神写树剖萌新瑟瑟发抖...然而学完了树剖发现也可以用Tarjan求LCA...→_→不过树剖边权变点权的思想还是有用的。

    LCA+二分答案+树上差分序列检验

    差分序列的具体实现:

    遍历路径长度大于二分中值的(不合法的)询问,记其总数为tot,对其中每个节点u指向节点v的询问:cnt[u]++; cnt[v]++; cnt[LCA(u,v)]-=2;
    然后DFS,对于节点u,加深,记rtn[u]=cnt[u]+所有子节点的rtn值之和,这样rtn[u]即表示经过节点u(所对应的原树中的边)的(不合法的)路径的条数,若==tot则表示所有不合法的边都经过这一路径。
    在此基础上,如果改造这条边为虫洞能使最长的路径<=二分中值(此时所有其他路径也<=二分中值),则可行。

    我使用的是Tarjan离线算法预先求出所有询问的原路径长度和LCA。

    特别提示C++党不要用vector建图,否则只能过一半的点。

    测试数据 #0: Accepted, time = 0 ms, mem = 34608 KiB, score = 5
    测试数据 #1: Accepted, time = 15 ms, mem = 34608 KiB, score = 5
    测试数据 #2: Accepted, time = 0 ms, mem = 34608 KiB, score = 5
    测试数据 #3: Accepted, time = 15 ms, mem = 34608 KiB, score = 5
    测试数据 #4: Accepted, time = 15 ms, mem = 34648 KiB, score = 5
    测试数据 #5: Accepted, time = 15 ms, mem = 34692 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 34744 KiB, score = 5
    测试数据 #7: Accepted, time = 0 ms, mem = 34612 KiB, score = 5
    测试数据 #8: Accepted, time = 15 ms, mem = 34612 KiB, score = 5
    测试数据 #9: Accepted, time = 15 ms, mem = 34604 KiB, score = 5
    测试数据 #10: Accepted, time = 93 ms, mem = 34840 KiB, score = 5
    测试数据 #11: Accepted, time = 109 ms, mem = 34904 KiB, score = 5
    测试数据 #12: Accepted, time = 140 ms, mem = 37884 KiB, score = 5
    测试数据 #13: Accepted, time = 156 ms, mem = 38356 KiB, score = 5
    测试数据 #14: Accepted, time = 218 ms, mem = 38824 KiB, score = 5
    测试数据 #15: Accepted, time = 218 ms, mem = 39296 KiB, score = 5
    测试数据 #16: Accepted, time = 156 ms, mem = 34844 KiB, score = 5
    测试数据 #17: Accepted, time = 203 ms, mem = 34868 KiB, score = 5
    测试数据 #18: Accepted, time = 203 ms, mem = 34900 KiB, score = 5
    测试数据 #19: Accepted, time = 687 ms, mem = 35508 KiB, score = 5
    Accepted, time = 2273 ms, mem = 39296 KiB, score = 100
    
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    #define MAXN 300010
    using namespace std;
    
    int N,M;
    
    struct edge
    {
        int u,v;
        int w;
    } E[MAXN<<1];
    int EC=0,Ef[MAXN<<1],En[MAXN<<1];
    
    void inline ADD_EDGE(int u,int v,int w)
    {
        E[++EC].u=u; E[EC].v=v; E[EC].w=w;
        En[EC]=Ef[u]; Ef[u]=EC; 
    }
    
    struct query
    {
        int u,v;
        int LCA;
        int l;
        bool operator > (const query& q) const
        {
            return l>q.l;
        }
    } Q[MAXN<<1];
    int Qf[MAXN<<1],Qn[MAXN<<1]; 
    
    void inline ADD_QUERY(int u,int v,int i)
    {
        Q[i].u=u; Q[i].v=v; Q[i].LCA=Q[i].l=0;
        Qn[(i<<1)]=Qf[u]; Qf[u]=(i<<1);
        Qn[(i<<1)|1]=Qf[v]; Qf[v]=(i<<1)|1;
    }
    
    int dist[MAXN],P[MAXN],visited[MAXN],nw[MAXN],fa[MAXN];
    
    int FIND_SET(int u)
    {
        if(P[u]==u) return u;
        else return P[u]=FIND_SET(P[u]);
    }
    
    void DFS(int u)
    {
        P[u]=u;
        for(int i=Ef[u];i;i=En[i])
        {
            edge& e=E[i];
            if(e.v!=fa[u])
            {
                dist[e.v]=dist[u]+e.w;
                nw[e.v]=e.w;
                fa[e.v]=u;
                DFS(e.v);
                P[e.v]=u;
            }
        }
        visited[u]=true;
        for(int i=Qf[u];i;i=Qn[i])
        {
            
            query& q=Q[i>>1];
            if(!q.LCA)
            {
                if(q.v==u) swap(q.u,q.v);
                if(visited[q.v])
                {
                    q.LCA=FIND_SET(q.v);
                    q.l=dist[u]+dist[q.v]-2*dist[FIND_SET(q.v)];
                }
            }
        }
    }
    
    int inline Q_FIND(int minl)
    {
        int l=1,u=M;
        while(l<u)
        {
            int m=(l+u+1)>>1;
            if(Q[m].l>minl) l=m;
            else u=m-1;
        }
        return l;
    }
    
    int tot,cnt[MAXN],rtn[MAXN],min_nw;
    
    bool CHECK_DFS(int u)
    {
        rtn[u]=cnt[u];
        for(int i=Ef[u];i;i=En[i])
        {
            edge& e=E[i];
            if(e.v!=fa[u])
            {
                //fa[]在预处理DFS时已建立完成 
                if(CHECK_DFS(e.v)) return true;
                rtn[u]+=rtn[e.v];
            }
        }
        return (rtn[u]>=tot&&nw[u]>=min_nw);
    }
    
    bool inline CHECK(int t)
    {
        memset(cnt,0,sizeof(cnt));
        tot=Q_FIND(t);
        for(int i=1;i<=tot;i++)
        {
            cnt[Q[i].u]++;
            cnt[Q[i].v]++;
            cnt[Q[i].LCA]-=2;
        }
        min_nw=Q[1].l-t;
        return CHECK_DFS(1);
    }
    
    int MAX_W=0;
    
    int main()
    {
        memset(Ef,0,sizeof(Ef));
        memset(Qf,0,sizeof(Qf));
        
        scanf("%d%d",&N,&M);
        int u,v,w,l,m;
        for(int i=1;i<N;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            MAX_W=max(MAX_W,w);
            ADD_EDGE(u,v,w);
            ADD_EDGE(v,u,w);
        }
        for(int i=1;i<=M;i++)
        {
            scanf("%d%d",&u,&v);
            ADD_QUERY(u,v,i);
        }
        
        memset(visited,false,sizeof(visited));
        dist[1]=0; nw[1]=0; fa[1]=1;
        DFS(1);
         
        sort(Q+1,Q+1+M,greater<query>());
        
        l=Q[1].l-MAX_W;
        u=Q[1].l-1;
        while(l<u)
        {
            m=(l+u)>>1;
            if(CHECK(m)) u=m;
            else l=m+1;
        }
        
        printf("%d\n",l);
        
        return 0;
    }
    
  • 0
    @ 2016-09-13 17:33:46

    T了一个点……我理解为写dfs在vijos上爆栈了吧,然而不想改了……bzoj AC。
    二分答案 + 树链剖分 + 差分标记验证。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <ctime>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <string>
    using namespace std;

    #define MAXN 300005

    int ch=0;
    inline void read(int &a) {
    while (ch<'0' || ch>'9') ch=getchar();
    a=0;
    while (ch>='0' && ch<='9') {a=(a<<3)+(a<<1)+ch-'0';ch=getchar();}
    }

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

    int n,m,maxl=0,ecnt=0,head[MAXN],rs[MAXN],rt[MAXN],rd[MAXN],len[MAXN];

    int ss[MAXN],maxs[MAXN],son[MAXN],fa[MAXN],dep[MAXN],dis[MAXN];
    int top[MAXN],tid[MAXN],dfn=0;

    int t[MAXN],rlen[MAXN];

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

    inline void input() {
    read(n);read(m);
    for (int i=1,u,v,w;i<n;i++) {
    read(u);read(v);read(w);
    add(u,v,w);
    }
    for (int i=1;i<=m;i++) {
    read(rs[i]);read(rt[i]);
    }
    }

    void finds(int x) {
    son[x]=maxs[x]=0;
    ss[x]=1;
    for (int now=head[x],v;now;now=e[now].next) {
    v=e[now].to;
    if (v!=fa[x]) {
    rd[v]=e[now].w;
    dis[v]=dis[x]+e[now].w;
    fa[v]=x;
    dep[v]=dep[x]+1;
    finds(v);
    ss[x]+=ss[v];
    if (ss[v]>maxs[x]) {
    maxs[x]=ss[v];
    son[x]=v;
    }
    }
    }
    }

    void link(int x,int anc) {
    tid[x]=++dfn;
    rlen[dfn]=rd[x];
    top[x]=anc;
    if (son[x]) {
    link(son[x],anc);
    for (int now=head[x],v;now;now=e[now].next) {
    v=e[now].to;
    if (v!=fa[x] && v!=son[x]) {
    link(v,v);
    }
    }
    }
    }

    inline void init() {
    input();
    fa[1]=1;
    dis[1]=0;
    dep[1]=1;
    finds(1);
    link(1,1);
    }

    int getLCA(int u,int v) {
    while (top[u]!=top[v]) {
    if (dep[top[u]]>dep[top[v]]) {
    swap(u,v);
    }
    v=fa[top[v]];
    }
    if (dep[u]<dep[v]) return u;
    return v;
    }

    inline void getlen() {
    for (int i=1;i<=m;i++) {
    int lca=getLCA(rs[i],rt[i]);
    len[i]=dis[rs[i]]+dis[rt[i]]-(dis[lca]<<1);
    maxl=max(maxl,len[i]);
    }
    }

    inline void mark(int x) {
    int u=rs[x],v=rt[x];
    while (top[u]!=top[v]) {
    if (dep[top[u]]>dep[top[v]]) {
    swap(u,v);
    }
    // mark top[v] + ~ v +
    t[tid[top[v]]]++,t[tid[v]+1]--;
    v=fa[top[v]];
    }
    if (dep[u]>dep[v]) {
    swap(u,v);
    }
    // mark u - ~ v +
    t[tid[u]+1]++,t[tid[v]+1]--;
    }

    inline bool check(int x) {
    memset(t,0,sizeof(t));
    int cnt=0;
    for (int i=1;i<=m;i++) {
    if (len[i]>x) {
    mark(i);
    cnt++;
    }
    }
    for (int i=1;i<=n;i++) {
    t[i]+=t[i-1];
    if (t[i]>=cnt && maxl-x<=rlen[i]) return 1;
    }
    return 0;
    }

    int main() {
    //freopen("transport.in","r",stdin);
    //freopen("transport.out","w",stdout);
    init();
    getlen();
    int l=0,r=maxl,mid;
    while (l<r) {
    mid=(l+r)>>1;
    if (check(mid)) r=mid;
    else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
    }

  • -1
    @ 2016-07-22 10:29:51

    同样的程序,bzoj上ac,这tle= =

  • -1
    @ 2015-11-14 19:09:41

    看到这题秒想出LCA。可是...我考试前5 6天才接触的LCA。。。然后我已经前年考过了就懒了下...我擦,然后我就哭了。

    于是只好打了个spfa+快排预先读入每个点计算所有计划所需要的时间。用了类似底楼的贪心...希望能骗点分吧。呜呜呜呜

    day2炸的飞起。还在浙江....

  • -1
    @ 2015-11-11 09:18:06

    二分答案之后求树上路径交……树剖+差分数组比较好办呐……考场上狂撸倍增QWQ

  • 1

信息

ID
1983
难度
8
分类
(无)
标签
递交数
2434
已通过
328
通过率
13%
被复制
8
上传者