传送门 官方题解 A. 商汤的AI伴游小精灵 提意就是删去树上的两个节点，使非子节点（包括单节点）的数量最少。 显然是删去度最大的两个节点，当这两个节点有联通关系时，需要在答案上减一。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> #include<string.h> #include<iomanip> #define ll long long #define Max(a,b) ((a) > (b) ? (a) : (b)) #define INF 0x3f3f3f3f #define N 5100 const int mod = 1e9+7; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} int n; vector<int> tre[N]; struct node { int sum,id; }rk[N]; bool cmp(node a,node b){ if(a.sum==b.sum) return a.id>b.id; else return a.sum>b.sum; } bool check(int a,int b){ for (int i=0;i<tre[a].size();i++) if(tre[a][i] == b) return 1; return 0; } int main(){ scanf("%d",&n); int x,y; for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); tre[x].push_back(y); } for (int i=1;i<=n;i++) rk[i].sum = tre[i].size(),rk[i].id = i; sort(rk+1,rk+n+1,cmp); int ans=rk[1].sum+rk[2].sum; if(check(rk[1].id,rk[2].id) || check(rk[1].id,rk[2].id)) ans--; printf("%d\n",ans); return 0; }B. 商汤AI园区的n个路口（简单) 在这题中，树退化成了一条链，且m<=50 , 可以考虑动态规划。 定义dp[i][j]为第i个路口信号频段为j的情况，有转移： dp[i][j] +=d[i-1][k] , gcd(k,j)!=wi
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> #include<string.h> #include<iomanip> #define ll long long #define Max(a,b) ((a) > (b) ? (a) : (b)) #define INF 0x3f3f3f3f #define N 60 const int mod = 1e9+7; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} int n,m; ll dp[N][N],ans=0;; int g[N][N],a[N][N][N]; inline void init(){ for (int i=1;i<=50;i++) for(int j=1;j<=50;j++) g[i][j]=gcd(i,j); scanf("%d%d",&n,&m); int u,v,w[N]; for(int i=1;i<n;i++) scanf("%d%d%d",&u,&v,&w[i]); memset(a,0,sizeof a); memset(dp,0,sizeof dp); for (int k=1;k<n;k++) for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(g[i][j]!=w[k] && g[i][j]<=m) a[k][i][j]=1; } inline void solve(){ for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) dp[1][i]=a[1][i][j]; for (int k=1;k<n;k++) for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if (a[k][i][j]) dp[k+1][j] += dp[k][i]%mod; for(int i=1;i<=m;i++) ans+=dp[n][i]%mod; printf("%lld\n", ans%mod); } int main(){ init(); solve(); return 0; }C. 商汤AI园区的n个路口（中等） 这时候m<=1000，且数据变为一棵树了，这时候考虑树形dp。 因为每条边的w不同，用g[i][w]记录下gcd(i,j)!=w的所有j，然后做树上dp即可
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<cstdlib> #include<string.h> #include<iomanip> #define ll long long #define Max(a,b) ((a) > (b) ? (a) : (b)) #define INF 0x3f3f3f3f #define N 1010 const int mod = 1e9+7; typedef std::pair<int, int> pii; typedef std::pair<ll, ll> pll; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} using namespace std; const int maxn = 1000 + 7 ; vector<pii> G[maxn]; ll dp[maxn][maxn], sum[maxn]; vector<int> g[maxn][maxn]; int n, m; void dfs(int u, int fa){ for(int i = 1; i <= m; i++) dp[u][i] = 1; for(auto &v : G[u]){ if(v.first != fa){ dfs(v.first, u); for(int j = 1; j <= m; j++){ int tmp = sum[v.first]; for(int k : g[j][v.second]){ tmp = (tmp - dp[v.first][k] + mod) % mod; } dp[u][j] = dp[u][j] * tmp % mod; } } } sum[u] = 0; for(int i = 1; i <= m; i++) sum[u] = (sum[u] + dp[u][i]) % mod; } int main(){ scanf("%d%d", &n, &m); for(int i = 2; i <= n; i++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u].push_back(pii(v, w)); G[v].push_back(pii(u, w)); } for(int i = 1; i <= m; i++){ for(int j = 1; j <= m; j++){ g[i][gcd(i, j)].push_back(j); } } for(int i = 1; i <= m; i++){ for(int j = 1; j <= m; j++){ sort(g[i][j].begin(), g[i][j].end()); g[i][j].erase(unique(g[i][j].begin(), g[i][j].end()), g[i][j].end()); } } dfs(1, 0); printf("%lld\n", sum[1]); return 0; }D. 商汤AI园区的n个路口（困难） 莫比乌斯反演，冲不动了
