题解 - Vijos

4

passer_1 LV 9 @ 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

kevindurant LV 8 @ 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

Hory LV 10 @ 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

PowderHan LV 10 @ 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

独孤无影手andy LV 8 @ 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

linhui LV 9 @ 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

explodingnerk LV 8 @ 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

可燃冰 LV 8 @ 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

rourou LV 9 @ 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;
}
```

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

太感谢了！！！易懂！！！模模模！！！

1

fhcxn LV 8 @ 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。。。。。。

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

Vijos似乎刚刚改大栈空间，试试重交一遍？

1

TenderRun LV 10 @ 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

Firstlast LV 10 @ 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，我也是这么写的。
jimmy19990 @ 2015-11-11 12:08:34

Jump ;)
whcnm @ 2016-11-05 11:01:19

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

0

nonamenotitle LV 6 @ 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

liuzikai LV 8 @ 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

Firstlast LV 10 @ 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

151052 LV 9 @ 2016-07-22 10:29:51

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

-1

冲啊小笼包 LV 9 @ 2015-11-14 19:09:41

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

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

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

-1

function2 LV 10 @ 2015-11-11 09:18:06

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

题解

18 条题解

运输计划

信息

状态

开发

支持

题解

18 条题解

运输计划

信息

状态

开发

支持

还没有账户？

登录