HDU 6203 ping ACM/ICPC 2017 Shenyang Online（LCA+貪心）

ping ping ping

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 65    Accepted Submission(s): 17

Problem Description

n servers, some servers connect to the gateway whose IP address is 0 directly. All servers are connected with each other by

n netting twines. It is said that this structure is favorable for maintaining physical problem of servers.

But because of an unexpected rainstorm, the computer room was destroyed by a terrible thunderclap!

Our maintainer Bittersweet found that many servers were not able to be visited, so he hurried to the computer room to lookup the reason. After several hours, Bittersweet realized that some net gape of servers were broken by thunderclap. However, there were too many servers to find out all the broken net gapes quickly. So he came up with an idea to assess the damaged condition roughly. Bittersweet decided to turn on some servers and ping other servers randomly, then record the unsuccessful pairs of servers.

Now he need a program to analyze the record to confirm what is the

minimum number of servers whose net gape was destroyed by thunderclap. Can you help him to complete this work?

Input

There are at most 20 test cases.

In each test case, the first line is an integer

n (

3≤n≤104), denoting the number of servers. The IP address of these servers is

1…n.

Then follows

n lines, each line contains two integers

u and

v (

0≤u,v≤n), denoting that the server whose IP address is

u is connected with the server whose IP address is

v by netting twine initially.

After those, there is one line contains only an integer

p (

p≤50000), denoting the number that Bittersweet uses ping.

Then follows

p lines, each line contains two integers

U and

V , denoting when using server

U to ping server

V, it returned unsuccessful.

Output

x in a line, denoting at least

x servers whose net gape were broken.

Sample Input

4

1 0

4 2

2 0

3 2

2

1 3

2 1

Sample Output

Source

​​2017 ACM/ICPC Asia Regional Shenyang Online​​

        現在想來好簡單，還是太菜了……

        大緻題意：給你一個樹形網絡，然後再給出一些點對，意思是這些點對不能互相連通，然後問最少壞掉多少個點，能夠滿足這些不連通的性質。

        一開始的想法是對于一個點對，然後把路徑上所有的點都加一，然後對應删除點權最大的點，然後相應剪掉關聯的點對造成的貢獻。但是很明顯，确定了點權最大的點，但是無法在可行的時間内确定該點關聯哪些點對，于是就不知道該怎麼做了。其實即使能夠解決這個問題，也不一定能夠對，因為當有多個點權都是最大的時候，并不是随便取就能滿足最優值的。是以還得另外考慮。

#include<bits/stdc++.h>
#define N 10100
using namespace std;

struct query{int u,v,dep,lca;};

bool operator<(query a,query b)                //按照lca深度排序
{
    return a.dep<b.dep;
}

priority_queue<query> que;
vector<int> g[N];
bool vis[N];
int n;

namespace LCA
{
    int dp[N][20],dep[N];

    void init()
    {
        memset(dp,0,sizeof(dp));
        memset(dep,0,sizeof(dep));
    }

    inline void dfs(int x,int fa)
    {
        for(int i=0;i<g[x].size();i++)
        {
            int y=g[x][i];
            if (y==fa) continue;
            dep[y]=dep[x]+1;
            dp[y][0]=x; dfs(y,x);
        }
    }

    void ST()
    {
        for(int j=0;j<17;j++)
            for(int i=1;i<=n;i++)
                dp[i][j+1]=dp[dp[i][j]][j];
    }

    inline int lca(int u,int v)
    {
        if (u==v) return u;
        if (dep[v]>dep[u]) swap(u,v);
        for(int i=18;i>=0;i--)
            if (dep[dp[u][i]]>=dep[v]) u=dp[u][i];
        if (u==v) return u;
        for(int i=18;i>=0;i--)
            if (dp[u][i]!=dp[v][i]) u=dp[u][i],v=dp[v][i];
        return dp[u][0];
    }
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if (!vis[y]&&LCA::dep[y]>LCA::dep[x]) dfs(y);            //隻能往下走，要判斷深度
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        int ans=0;LCA::init();
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        LCA::dfs(0,-1); LCA::ST();
        int q; scanf("%d",&q);
        while(q--)
        {
            int u,v,lca,dep;
            scanf("%d%d",&u,&v);
            lca=LCA::lca(u,v);
            dep=LCA::dep[lca];
            que.push(query{u,v,dep,lca});
        }
        while(!que.empty())
        {
            int u=que.top().u,v=que.top().v;
            int lca=que.top().lca; que.pop();
            if (vis[u]||vis[v]) continue;            //如果點對已經不連通那麼沒必要再删除
            ans++; dfs(lca);                    //否則删除，并标記lca的子樹
        }
        printf("%d\n",ans);
    }
    return 0;
}