Codeworks round 801 (Div. 2) and epic Institute of technology round D. tree queries (tree DP)

subject

t(t<=1e4) Group example , Give one at a time n(n<=2e5) A rootless tree with two dots ,

The author thinks of a tree point , Record as point x,

Find the minimum number of points k, Make no matter x What point is it ,

You ask this k A point and x Distance of , After the questioner answers one by one ,

You can find out what the person who made the question thought x What's the point ,

You don't need to actually give a dot , Just output k The minimum value of

Source of ideas

dls Code 、jiangly Code

Answer key

I was defeated in the game , After the game, I did find a counterexample of the code I wrote , Maybe it would be much better to write a match in the game

First in the race The special sentence was dropped n=1 and n=2, Then I played with my hands and found ,

If Fix two points on the tree u、v, It is equivalent to marking the tree u To v This chain , The points on this chain can be uniquely determined ,

To the point on this chain , If there is only one with the same depth , It can also be uniquely identified , If it is larger than one, it cannot be marked ,

There is no obvious greedy strategy , So consider tree dp,dp[i] It means that only i At least a few points should be marked on this subtree ,

If marked u、v None of them are leaves , Actually, it's not as good as marking u、v They are all excellent leaves , because It can be extended to both ends

And found that , If there is a chain in the subtree , There is a chain that can be marked without points , There is a chance of exemption

Like trees (1-2,2-3,2-4), If it's marked 1 Number point and 3 Number point , actual 4 The number point is not marked , Because it can be uniquely determined

So the race starts with a leaf dfs, Then pair the subtree dp,

Finally, I decided whether the root needs to be marked , And then I hung up , There are still two tips I didn't think of it

Use leaves as roots dfs The problem is , When this root is directly connected by a degree =2 At the time of ,

I have to record this degree =2 In the subtree of the point , Has this exemption opportunity been used ,

If degree =2 The point of is connected by another degree =2 The point of , You have to think recursively ,

therefore , actually 2 The degree point is to be shrunk , This determines the writing method of this problem ：

1. One chain , In fact, only one point at the end of the chain can be determined , Special judgment

2. From a certain degree >=3 It's the beginning of dfs( If from the leaves / degree =2 It's the beginning of dfs There will be the above recursive consideration , It will be difficult to write )

Experience

Codeforces Global Round 19 F.Towers( Tree form dp)  And this tree dp It might be similar to

At that time, I didn't expect to put the biggest h Point as root to make a tree dp,wa A few rounds and then got through

I think the difficulty may be 2100-2400 Between ,dp We still need to play with more hands and find more properties , And practice shooting to find counterexamples

Code 1

Code 1 According to the competition wa The code changed , Actually, it can be written more succinctly , Such as code 2 Shown

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N=2e5+10,INF=0x3f3f3f3f;
int t,n,m,x,y,dp[N],col[N],rt,mx;
bool link[N];
vector<int>e[N];
void dfs(int u,int fa){
    dp[u]=0;
    link[u]=1;
    int son=0;
    bool haslinkson=0;
    for(auto &v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];
        son++;
        link[u]&=link[v];
        haslinkson|=link[v];
    }
    if(son>1)link[u]=0;
    if(!son)dp[u]=1;
    if(son>1 && haslinkson)dp[u]--;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            e[i].clear();
        }
        mx=0;
        for(int i=1;i<n;++i){
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
            e[y].push_back(x);
            mx=max(mx,(int)e[x].size());
            mx=max(mx,(int)e[y].size());
        }
        if(n==1 || n==2){
            printf("%d\n",n-1);
            continue;
        }
        if(mx<=2){
            puts("1");
            continue;
        }
        int ans=n;
        for(int i=1;i<=n;++i){
            if(((int)e[i].size())==3){
                rt=i;
                dfs(rt,-1);
                ans=min(ans,dp[rt]);
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
888
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
*/

Code 2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N=2e5+10,INF=0x3f3f3f3f;
int t,n,m,x,y,dp[N],mx;
vector<int>e[N];
void dfs(int u,int fa){
    dp[u]=0;
    int link=0;
    for(auto &v:e[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];
        if(!dp[v])link++;
    }
    dp[u]+=max(link-1,0);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            e[i].clear();
        }
        mx=0;
        for(int i=1;i<n;++i){
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
            e[y].push_back(x);
            mx=max(mx,(int)e[x].size());
            mx=max(mx,(int)e[y].size());
        }
        if(n==1 || n==2){
            printf("%d\n",n-1);
            continue;
        }
        if(mx<=2){
            puts("1");
            continue;
        }
        for(int i=1;i<=n;++i){
            if(((int)e[i].size())>=3){
                dfs(i,-1);
                printf("%d\n",dp[i]);
                break;
            }
        }
    }
    return 0;
}
/*
888
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
*/