Les arcanes sont mises à jour tous les trois mois!!Applaudissez, applaudissez

Et quelques mises à jour surDPArticle de(RioTianExtase)

Maintenant Dépêchez - vous d'étudier et de revoir la forme de l'arbreDP....

ArbreDPBase:Here,CFPartie supérieure de l'arbreDPExercices:Here


\[QAQ
\]

Apprendre la forme de l'arbreDPAvant,Nous devons d'abord trouver un problème,Qu'est - ce qu'un arbre?D'après ce que nous avons appris dans le cours de théorie des graphes, nous savons,Les graphiques circulaires connectés sont appelés arbres.Et l'arbre peut être considéré comme une structure fractale,Cela signifie que notre arbre peut être défini Récursivement,Chaque sous - arbre de l'arbre est aussi un arbre entier,Et cette structure est naturellement adaptée à la récursion.

Plus précisément,,Dans la planification dynamique des arbres,En général, nous faisons d'abord l'arbre des opérateurs avant de fusionner,Similaire à la traversée post - ordre de l'arbre en termes d'implémentation,Tout d'abord à travers le Sous - arbre,Passez la valeur du sous - arbre au père après la traversée.En termes simples, notre processus de programmation dynamique est probablement un accès récursif d'abord à tous les sous - arbres,Fusionner à nouveau sur la racine.

Après avoir compris l'idée de base de la planification dynamique des arbres,Faites des arbres classiquesDPType de question

【Exemple classique】

【Taille du sous - arbre】

Description

Voici un arbre avec $n$ Un arbre pointillé($1$ Le point est le noeud racine),S'il vous plaît $i$ Est la taille du sous - arbre de la racine .

Ce problème est un exemple de notre programmation dynamique arborescente , C'est très simple, bien sûr. , Juste une course. \(DFS\) On peut le trouver. .

Détails:

  • Mise en place \(f_i\) Par \(i\) Est la taille du sous - arbre de la racine ,Et \(f[i] = \sum f[k] + 1\) ,Parmi eux \(k\) Pour \(i\) Sous - noeud .

    Si écrit en pseudo - Code , À peu près comme ça.

void dfs(u){
if (u C'est une feuille. ) f[u] = 1 return
for (v - Oui. u Fils de ){
dfs(v)
f[u] += f[v]
}
f[u] += 1 // En soi
}

C'est l'arbre le plus simple. DPC'est, Vous sentez - vous traverser le Sous - arbre en premier? , Qu'en est - il d'un processus de programmation dynamique qui transfère la valeur du sous - arbre à son père après la traversée? ?

【 Le point d'équilibre de l'arbre 】

Description

Je t'en donne un. $n$ Un arbre pointillé, Trouver le point d'équilibre de l'arbre et le nombre maximum de noeuds du sous - arbre après la suppression du point d'équilibre . Le soi - disant point d'équilibre , Se réfère à un point dans l'arbre , Supprimer le point , Faire en sorte que les autres blocs connectés , Le plus grand bloc connecté a la plus petite taille de bloc .

Pour résoudre ce problème, Nous devons d'abord déterminer l'état , La question est simple. , En général, c'est une question. , Donc nous avons commencé \(F[i]\)​​ Supprimer pour \(i\)​​ Taille du bloc du bloc de raccordement le plus grand après le point No. . Ensuite, nous suivons le schéma de la question précédente. \(f[i]\)​​ Par \(i\)​​ Est la taille du sous - arbre de la racine , C'est très simple. \(F[i]=max(n−f[i],max(f[k]))\)​​,Parmi eux \(k\)​​ - Oui. \(i\)​ Sous - noeud de .C'est parce que,Supprimer \(i\)​ Après le point , Le reste de notre bloc de connexion est soit \(i\) Sous - arbre de,Ou bien \(i\)​ Le bloc de connexion où se trouve le père de .

En termes simples , C'est - à - dire après la suppression d'un noeud , Son fils est devenu un bloc de connexion indépendant , Donc le plus gros bloc de connexion est max(x Tous les fils de size,n - f[x])

Je vous emprunte une cuillère. dalao Graphique

Donc tout ce que nous avons à faire est d'utiliser la méthode de la première question pour calculer la taille du sous - arbre de chaque point. ,Encore. \(DFS\) Calculer chaque point encore et encore \(F[i]\)​ , Le plus petit point est le point d'équilibre de notre arbre. .

【Mise en œuvre du Code】

 vector<int>e[N];
int ans, idx, f[N];
void dfs(int u, int fa) {
f[u] = 1;
int mx = 0;
for (int v : e[u]) {
if (v == fa)continue;
dfs(v, u);
f[u] += f[v];
mx = max(mx, f[v]);
}
mx = max(mx, n - f[u]);
if (ans > mx) ans = mx, idx = u;
}

Un bal sans patron. ( Ensemble indépendant maximum de l'arbre )

Description

Oui. $n$ Personnel ,Le numéro est $1\sim n$ , Leur relation est comme un arbre basé sur le patron. , Le noeud parent est le patron direct du noeud enfant . Chaque employé a un indice de bonheur , Avec un entier $H_i$ Donner, Il y a une fête d'anniversaire. ,Mais, Aucun employé n'est prêt à assister à la réunion avec son superviseur immédiat . Sous réserve que cette condition soit remplie , L'organisateur souhaite inviter une partie du personnel , Maximiser l'indice de bonheur total de tous les participants , Trouvez ce maximum. .

C'est ici. ArbreDPBase Je l'ai dit.

Résumons le sujet. , Aucun employé n'assistera à la réunion avec son patron. , C'est - à - dire qu'il n'y a pas de bord sur l'arbre qui relie les deux points. , En d'autres termes, ce que cette question nous demande vraiment, c'est Ensemble indépendant du poids maximal de l'arbre .

Le grand homme a mentionné sur son blog ——— Coloration noir et blanc , C'est - à - dire choisir une couche sur l'arbre et ne pas choisir une telle cupidité .

Mais il est facile de prouver que la simple coloration noir et blanc n'est pas correcte. ,Comme le montre la figure ci - dessous, Sur la gauche, il y a une coloration noir et blanc. , A droite, c'est le résultat d'une solution positive. . Les points noirs indiquent qui vient. , Les points blancs indiquent ceux qui ne viennent pas. , Dans ce cas, nous supposons que tout le monde a le même indice de bonheur par défaut. .

Donc, nous devons être honnêtes et aller de l'avant, pas à pas. .Nous avons découvert \(i\)​ En fait, le fait de cliquer ou de ne pas sélectionner le signe affecte le résultat du sous - arbre. , Nous devons clarifier cette couche d'influence dans l'état .Donc nous utilisons \(f[i][0]\)​ Indique non sélectionné \(i\)​ Au bal de promo. \(i\)​ Le plus grand indice de bonheur que les points et leurs sous - arbres peuvent choisir ; \(f[i][1]\) Choix de la représentation \(i\) Au bal de promo. \(i\) Le plus grand indice de bonheur que les points et leurs sous - arbres peuvent choisir . Ensuite, nous avons pensé à la façon de transférer , Quand on ne choisit pas \(i\)​ Au bal de promo. , Ses fils peuvent ou non participer , Il y a donc l'équation de transfert suivante

Équation de transfert :\(f[i][0] = \sum(max(f[k][0],f[k][1]))\)​​ ,Parmi eux \(k\) - Oui. \(i\)​ Fils de ;

  • Élu. \(i\) Au bal , Son fils ne peut pas participer. ,Alors... \(f[i][0] = \sum f[k][0] + H_i\)

Où nos Conditions limites sont \(i\) Quand c'est une feuille \(f[i][0] = 0,f[i][1] = H_i\)

Notre dernière réponse est \(ans = max(f[root][0],f[root][1])\)

Et si vous devenez le plus grand ensemble indépendant de l'arbre, il suffit de laisser notre $ H_i = 1$​ C'est tout ce qu'il faut. .

【AC Code】

const int N = 1e4 + 10;
vector tr[N];
int f[N][2], v[N], Happy[N], n;
void dfs(int u) {
f[u][0] = 0; f[u][1] = Happy[u];
for (auto v : tr[u]) {
dfs(v);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> Happy[i];
for (int i = 1, x, y; i < n; ++i) {
cin >> x >> y;
v[x] = 1;// x has a father
tr[y].push_back(x);
}
int root;
for (int i = 1; i <= n; ++i)
if (!v[i]) {root = i; break;}
dfs(root);
cout << max(f[root][0], f[root][1]) << "\n";
}

Strategic game ( Couverture minimale de l'arbre )

Description

Je t'en donne un. $n$ Un arbre pointillé, Au plus un bord entre deux points . Si vous mettez un soldat sur un noeud , Pour qu'il puisse garder le côté connecté , Combien de soldats au moins? , Pour garder tous les côtés .

Cette question et la précédente : Un bal sans patron. ( Ensemble indépendant maximum de l'arbre ) Ça me ressemble. ,Liens vers les sujets:Here

Sont capables de découvrir \(i\) Le nombre de points ou de non - points est le résultat qui affecte le Sous - arbre . Mais contrairement à la question précédente, le père d'un fils ne peut pas choisir en même temps : Un fils et un père ne peuvent pas être différents en même temps. .

Alors notre état sera clair. ,

  • Mise en place \(f[i][0]\) Non. \(i\) Mettez les soldats sur le point n° 1 et utilisez \(i\) Nombre minimum de soldats vus de chaque côté de la racine ;
  • Mise en place \(f[i][1]\) Pour \(i\) Mettez les soldats sur le point n° 1 et utilisez \(i\)​ Nombre minimum de soldats vus de chaque côté du sous - arbre racine .

Ensuite, envisageons le transfert. ,

  • Quand \(i\)​ Quand vous commandez de ne pas libérer les soldats , Son fils doit libérer ses soldats. ,Alors... \(f[i][0] = \sum f[k][1]\)​ ;

  • Quand \(i\) Quand vous commandez de ne pas libérer les soldats , Son fils peut libérer les soldats. , Ou pas de soldats. ,Alors...

    \(f[i][1] = 1 + \sum(min(f[k][0],f[k][1]))\)

Notre dernière réponse est :\(ans = min(f[root][0],f[root][1])\)​

C'est la solution au problème de la couverture minimale de l'arbre .

vector<int>e[N];
int f[N][2];
bool st[N];
void dfs(int u) {
st[u] = 1;
f[u][0] = 0, f[u][1] = 1;
for (int i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
if (st[v]) continue;
dfs(v);
f[u][0] += f[v][1];
f[u][1] += min(f[v][0], f[v][1]);
}
}
int main() {
int n, m, k, x;
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; ++i) {
scanf("%d:(%d)", &m, &k);
while (k--) {
scanf("%d", &x);
e[m].push_back(x), e[x].push_back(m);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (st[i]) continue;
dfs(i);
ans += min(f[i][0], f[i][1]);
}
printf("%d\n", ans);
memset(st, 0, sizeof(st));
for (int i = 0; i < N; ++i) e[i].clear();
}
}

Cell Phone Network ( Ensemble minimal dominant d'arbres )

Liens vers les sujets:Here

Description

Je t'en donne un. $n$ Un arbre pointillé, Au plus un bord entre deux points .Si le $i$ Tour de signalisation de déploiement de points , Pour qu'il et tous les points qui lui sont connectés reçoivent un signal . Trouver le nombre minimum de Tours à déployer pour que tous les points reçoivent des signaux .

Cette question peut être considérée comme une version améliorée des deux questions précédentes. , Sélectionnez ou non l'une des deux questions précédentes , Ça n'affecte que le choix ou non de son fils. ; Mais dans cette question, , Un choix ou un non - choix affecte non seulement le fils, mais aussi le père. , C'est un peu plus compliqué dans la conception de l'état. .

  • Mise en place \(f[i][0]\) Indique le point de sélection \(i\),Et avec \(i\) Nombre minimum de Tours déployées pour couvrir chaque point du sous - arbre racine ;

  • Mise en place \(f[i][1]\) Indique qu'aucun point n'est sélectionné \(i\),Et \(i\) Nombre minimum de Tours déployées couvertes par le fils ;

  • Mise en place \(f[i][2]\) Non. \(i\),Mais \(i\) Pas couvert par son fils. ,Et avec \(i\)​ Nombre minimum de Tours déployées pour couvrir d'autres points du sous - arbre racine ,

    En d'autres termes, \(i\) Le père doit choisir de le couvrir. \(i\).

Voyons comment faire le transfert. .

  • Quand nous choisissons \(i\) Heure de pointe ,\(i\) Le fils de point est facultatif , Et peut être écrasé et non écrasé , Donc nous avons

    \(f[i][0] = 1 + \sum(min(f[k][0],f[k][1],f[k][2]))\)

  • Quand nous ne choisissons pas \(i\),Et \(i\) Quand il n'est pas couvert , Ses fils sont couverts ou non. , Impossible de ne pas sélectionner et de ne pas être écrasé , Donc à ce moment - là,

    \(f[i][2] = \sum(f[k][1],f[k][0])\)

Le plus dur, c'est quand on ne choisit pas. \(i\),Et \(i\) Quand il est couvert , C'est la situation la plus compliquée. , C'est à ce moment - là. \(i\) Au moins un des fils de , Il y en a au moins un. \(f[k][0]\), C'est là que nous discutons de la situation. :

  1. Si c'est le cas, \(i\) Il y a un fils. \(k\) ,Oui. \(f[k][0] \le f[k][1]\) , Ce n'est pas pire. , Alors, choisissons - le. , Nos réponses reviennent \(f[i][1] = \sum(f[k][1],f[k][0])\)
  2. Si un tel fils n'existe pas, , C'est - à - dire pour tous les fils , Ça va empirer. , Alors, on va enregistrer ça. \(minn = min(f[k][0] ,f[k][1])\) , C'est - à - dire choisir celui qui perd le moins. , Notre réponse devient \(f[i][1] = \sum(f[k][1],f[k][0]) + minn\) .

C'est un peu compliqué. Voici un code de référence approximatif. :

void dfs(int x){
v[x] = 1;
f[x][0] = 1,f[x][1] = f[x][2] = 0;
int tmp = inf;
bool flag = 1;
for(int i = 0;i < e[x].size();++i){
int y = e[x][i];
if(vis[y]) continue;
dfs(y);
f[x][2] += min(f[y][1],f[y][0]);
f[x][0] += min(f[y][0],f[y][1],f[y][2]); // Surchargemin
if(f[y][0] <= f[y][1]){
flag = 0;
f[x][1] += f[y][0];
} else{
f[x][1] += f[y][1];
tmp = min(tmp,f[y][0] - f[y][1]);
}
}
if(flag) f[x][1] += tmp;
}
// Simpliste ACCode
const int N = 1e4 + 10, inf = 0x3f3f3f3f;
vector<int>e[N];
int ans;
bool vis[N]; void dfs(int u, int fa) {
bool f = 0;
for (int i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
if (v == fa) continue;
dfs(v, u); f |= vis[v];
}
if (!f && !vis[u] && !vis[fa])
vis[fa] = 1, ans += 1;
} int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
for (int i = 1, x, y; i <= n; ++i) {
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
cout << ans;
}

C'est là que notre problème de l'ensemble minimal de domination a été résolu. .

【 Pommier binaire 】 Problème de sac à dos sur l'arbre

Description

Il y a un pommier binaire , Si le nombre a une bifurcation , Ça doit être en deux. , C'est - à - dire qu'il n'y a pas de noeud avec un seul fils . Cet arbre $N$ Noeuds,Étiquette $1$ à $N$, Le nombre de racines doit être . Nous décrivons l'emplacement d'une branche en utilisant le nombre de noeuds reliés aux deux extrémités d'une branche. , Par exemple, voici un pommier avec quatre branches . Parce qu'il y a trop de branches , Besoin de taille . Mais certaines branches ont des pommes , Compte tenu du nombre de branches à conserver , Combien de pommes Pouvez - vous garder? .

Apprendre la forme de l'arbre DP Je l'ai rencontré. , Ça n'a pas marché.

Liens vers les sujets:Here

D'abord, la question dit que les pommes poussent sur les branches. , Donc nous pourrions aussi bien concevoir

  • \(a[i].l\) Représente une connexion \(i\) Nombre de pommes sur la branche avec son fils gauche
  • \(a[i].r\) Représente une connexion \(i\)​ Nombre de pommes sur la branche avec son fils droit

Nous sommes ici parce qu'en fin de compte, nous exigeons que le nombre maximum de pommes soit conservé compte tenu du nombre de branches à conserver. , Donc, nous pourrions aussi bien concevoir \(f[i][j]\) Exprimé par \(i\) Réservé au sous - arbre de la racine \(j\) Nombre maximum de pommes par branche . Ensuite, nous allons réfléchir à la façon de transférer , Notre transfert est divisé en quatre situations. :

  • Premièrement, pour \(i\), La situation dans laquelle ses sous - arbres gauche et droit sont conservés , À ce moment - là, \(i\) Réservé au sous - arbre de la racine \(j\) Une branche, On va mettre les sous - arbres à gauche et à droite. \(x\) Et \(y\) Une branche, Donc nous avons \(x+y+2=j\), Donc nous allons énumérer x,À ce moment - là, \(y=j−2−x\), Donc, à ce moment - là,

    \(f[i][j] = \max\limits_{x\in[0,j-2]}(f[l][x] + f[r][j - 2-x] + a[j].l + a[j].r)\)

  • Ensuite, pour le cas où seul le Sous - arbre gauche est conservé , À ce moment - là, \(i\) Réservé au sous - arbre de la racine \(j\) Une branche, Donc le Sous - arbre gauche reste \(j−1\) Une branche, Donc, à ce moment - là, \(f[i][j]=f[l][j−1]+a[j].l\)

  • Deuxièmement, pour le cas où seul le Sous - arbre droit est conservé , À ce moment - là, \(i\) Réservé au sous - arbre de la racine \(j\) Une branche, Le Sous - arbre droit doit donc être conservé. \(j−1\) Une branche, Donc, à ce moment - là, \(f[i][j]=f[r][j−1]+a[j].r\)

  • Enfin, il n'y a pas de sous - arbres gauche et droit. ,À ce moment - là, \(j=0\),C'est - à - dire \(f[i][0]=0\) .

C'est tout. \(4\) C'est si simple après ça? ? Nous allons maintenant mettre à jour la question , Si cet arbre n'est pas binaire, , Qu'est - ce qu'on fait si c'est un arbre à fourches? ? Supposons que ce soit \(k\) Arbre fourchu, La façon la plus simple de le faire est d'énumérer \(k−1\) Nombre de Fourches , Le reste est passé par la somme de \(j\) Calculer pour le transfert . Mais ça coûte beaucoup de temps. , C'est sûr. TLE De. C'est pour ça qu'on utilise l'idée d'un sac à dos dans un arbre. .

Commençons par un sous - arbre gauche fictif. , Triangle comme indiqué ci - dessous , Ensuite, nous avons fusionné le premier sous - arbre en tant que sous - arbre droit avec notre sous - arbre gauche fictif , Et mélanger le résultat de la fusion comme un sous - arbre gauche et boire un deuxième sous - arbre , Et fusionner les résultats fusionnés comme un sous - arbre gauche et un troisième sous - arbre ……Et ainsi de suite.. Et la fusion est l'énumération des arbres binaires ci - dessus \(x\) Processus. C'est - à - dire que nous continuons à fusionner les sous - arbres dans notre sous - arbre gauche. , Force à agir comme un arbre binaire .

C'est comme ça que ça se passe. :

\(f[u][j] = max(f[u][k] + f[v][j - k - 1] + a[u][v])\) Parmi eux \(f[u][j]\) Est représenté par i Réservé au sous - arbre de la racine j Nombre maximum de pommes par branche ,\(f[u][k]\) C'est notre“Sous - arbre gauche”Réserve \(k\) Nombre maximum de pommes par branche ,\(v\) - Oui. \(u\) Fils de ,Alors... \(f[v][j−k−1]\) C'est ce que nous sommes. “ Fils droit ”Réserve \(j−k−1\) Nombre maximum de pommes par branche , \(a[u][k]\) C'est le nombre de pommes à côté de nous. .

C'est l'idée d'un sac à dos dans un arbre. , J'espère que les élèves pourront comprendre .

【 Diamètre de l'arbre 】

Un autre article sur le diamètre des arbres est détaillé ici :Here,Exercice:Here

Description

Je t'en donne un. $n$ Un arbre pointillé, Chaque point de l'arbre a un poids . Définit la taille de la chaîne enfant d'un arbre comme : Somme des poids de tous les noeuds de cette sous - chaîne . Trouver la somme des poids des noeuds de la plus grande sous - chaîne de cet arbre .

Lien vers la question originale:Here

Les étudiants qui ont une bonne base de recherche l'ont peut - être vu. , Pas vraiment. DP , Deux fois. DFS Ça résout aussi les problèmes. .Plus précisément,, Commençons par n'importe quel point de l'arbre. , Trouvez le bord le plus long et commencez par un autre sommet de ce bord. DFS Le plus long côté trouvé est le diamètre de notre arbre. .

Cette fois. DFS , Commencez par un point, trouvez le premier long et le deuxième long ensemble. ? Ça ne marchera pas. , C'est un exemple. , Nous choisissons le premier long et le second long , Et nous avons découvert que nous étions passés par un côté public , Bien sûr que non. .

Deux fois. DFS Pourquoi est - ce vrai? , Faisons preuve de sensibilité. .

D'abord, tirons un coup d'oeil à notre processus. , On commence par trouver l'autre point le plus éloigné de lui. , À partir de là, trouvez la plus longue chaîne à partir de là. .

Tout d'abord, si le point que nous avons trouvé dans la première étape était sur notre plus longue chaîne, , La réponse doit être correcte. . Nous prouvons que le point que nous avons trouvé dans notre première étape doit être sur notre plus longue chaîne. ,Si ce n'est pas le cas,, Nous discutons de deux situations :

  • D'abord, la plus longue chaîne réelle a un point d'intersection avec la plus longue chaîne que nous avons trouvée. , Et se croisent sur la plus longue chaîne obtenue à la première étape . Si la chaîne la plus longue est affichée en bleu ci - dessous , S'il est plus long que le noir que nous avons trouvé . D'abord, parce que la première fois qu'on cherche, c'est la plus longue chaîne qui commence à la racine. ,Alors... \(a≥c\), Et la deuxième fois, c'est la plus longue chaîne que nous cherchions depuis le point où nous l'avons trouvée. ,Alors... \(b≥d\),Alors... \(a+b≥c+d\), C'est le bleu supposé qui est la chaîne la plus longue. \(a+b<c+d\) Contradictions!

  • Puis il y a la plus longue chaîne réelle qui a un point d'intersection avec la plus longue chaîne que nous avons trouvée. , Et se croisent sur la plus longue chaîne obtenue à l'étape 2 . Si la chaîne la plus longue est affichée en bleu ci - dessous , S'il est plus long que le noir que nous avons trouvé . D'abord, parce que la première fois qu'on cherche, c'est la plus longue chaîne qui commence à la racine. ,Alors... \(a≥c+t≥c\)​, Et la deuxième fois, c'est la plus longue chaîne que nous cherchions depuis le point où nous l'avons trouvée. ,Alors... \(b≥d+t≥d\)​,Alors... \(a+b≥c+d\)​, C'est le bleu supposé qui est la chaîne la plus longue. \(a+b<c+d\) Contradictions!

  • Enfin, il n'y a pas d'intersection entre la chaîne la plus longue réelle et la chaîne la plus longue que nous avons trouvée. . Si la chaîne la plus longue est affichée en bleu ci - dessous , S'il est plus long que le noir que nous avons trouvé . Sans perdre de vue la généralité , On pourrait le faire. \(d≥c\), Et puis notre autre chaîne, notre orange, a une longueur de \(L=a+x+y+d\) , Grâce à notre \(a+x\) Est la plus longue chaîne à partir de la racine ,Alors... \(a+x≥y+d\),Et \(d≥c\),Alors...

    \(L = a + x + y + d \ge y + d+ y+d \ge 2y + c + d > c + d\) ,

    Ceci est lié à \(c+d\)​​ C'est la chaîne la plus longue. ! Nous pouvons également analyser les contradictions d'un autre point de vue ,Nous savons que \(a+x\)​​ Est la plus longue chaîne à partir de la racine ,Alors... \(a≥b\)​,Et \(c+d>a+b\)​, Et peut - être qu'il pourrait \(d≥c\)​, Il y a au moins \(d>b\)​,Alors... \(x+y+d>b\),Alors... \(L=a+x+y+d>a+b\) ,Ceci est lié à \(a+b\) C'est la chaîne la plus longue qui est en contradiction avec le point que nous avons trouvé lors de notre première recherche. !

Deux fois. DFS La justesse de la méthode est indéniable. .

C'est fait. DFS Après, Ensuite, nous examinons comment nous pouvons résoudre ce problème en utilisant la programmation dynamique des arbres . Tout d'abord, nous savons que notre dernière réponse doit être de monter d'un point bas à un point élevé et de descendre comme notre graphique abstrait. , Et les deux côtés de la montée et de la descente doivent être les deux côtés les plus longs de ce point culminant. . C'est ce qui nous éclaire. , Nous avons créé \(f[i]\)​​​​ Représentation \(i\)​​​​ Longueur de la chaîne la plus longue du sous - arbre , On recommence. DFS En cours DP, Commençons par le traitement récursif \(i\)​​​​ Tous les fils de \(k\)​​​​,Et utiliser \(max(f[k])+a[i]\)​​​ Pour mettre à jour \(f[i]\)​​​,Parmi eux \(a[i]\)​​​ - Oui. \(i\)​​​ Poids du point . Et nous avons utilisé les plus grands et les plus petits \(f[k^′]\)​​ Et \(f[k^{″}]\)​ Pour mettre à jour les réponses \(ans=max(ans,f[k^′]+f[k^{″}]+a[i])\). Pour trouver le diamètre de notre arbre. .

Bien sûr, ce n'est pas un peu de poids, mais un peu de poids. , Après tout, les poids des points et des bords peuvent être convertis les uns aux autres en convertissant les points et les bords. .

Rinne Loves Edges ( Deuxième balayage et changement de racine )

Description

$Rinne$ Récemment, j'ai appris à maintenir rapidement des graphiques qui supportent l'insertion et la suppression de bords , Et répondre efficacement à des questions merveilleuses . Elle en a un maintenant. $n$ Noeuds $m(m=n-1)$ Graphique non rectiligne des bords des bandes , Chaque côté a un poids de bord Maintenant elle veut jouer à un jeu. : Sélectionner un “ Points importants ” $S$ , Puis supprimez sélectivement certains bords , Faire toutes les divisions dans le dessin original $S$ L'extérieur est $1$ Aucun point n'est accessible $S$.


Définit le coût de la suppression d'un bord comme le poids du bord pour ce bord ,Maintenant $Rinne$ Je vais te dire ce qu'il a choisi. “ Points importants ” Qui est - ce?, Elle veut savoir le moindre prix à payer pour finir le jeu. , Pour qu'elle puisse y arriver facilement. $rk1$ C'est!En retour, Elle va augmenter votre classement. .

D'abord, nous avons découvert que c'était un \(n\)​ Noeuds \(n−1\)​ Graphique non rectiligne des bords des bandes , Donc C'est un arbre. . Parce que les points importants sont connus , C'est pourquoi notre problème est que nous mettons le point final à la racine. , Nous voulons supprimer une série de bords de poids minimum , De sorte que la racine ne soit pas connectée à chaque feuille . Si vous y réfléchissez, \(i\)​ Sur le Sous - arbre de ce point, chaque feuille est \(S\)​ Déconnecté , Donc il y a deux situations , L'un est de mettre directement \(i\) Déconnecter de son fils ;Mais dans \(i\) Tous les noeuds foliaires ne sont pas accessibles sur le Sous - arbre de \(i\) .

Pour qu'on puisse définir \(f[i]\)​ Exprimé par \(i\)​ Coût minimal de la rupture de toutes les feuilles et racines d'un sous - arbre racinaire ,Alors... \(f[i]=∑(min(f[k],dis[i][k]))\),Parmi eux \(k\) - Oui. \(i\) Fils de ,\(dis[i][k]\) - Oui. \(i\) À \(k\) Poids latéral .

C'est un problème facile à résoudre. . Examinons une variante du problème. , Voici la description du sujet :

Description

$Rinne$ Récemment, j'ai appris à maintenir rapidement des graphiques qui supportent l'insertion et la suppression de bords , Et répondre efficacement à des questions merveilleuses . Elle en a un maintenant. $n(1\le n\le 1000)$ Noeuds $m(m=n-1)$ Graphique non rectiligne des bords des bandes , Chaque côté a un poids de bord $w_i$ Maintenant elle veut jouer à un jeu. : Sélectionner un “ Points importants ” $S$, Puis supprimez sélectivement certains bords , Faire toutes les divisions dans le dessin original $S$ L'extérieur est $1$ Aucun point n'est accessible $S$.


Définit le coût de la suppression d'un bord comme le poids du bord pour ce bord , En raison de capacités limitées , Le coût total des bords coupés ne doit pas dépasser $m$, Et réduire au minimum le coût le plus élevé des bords coupés . Dans des conditions de capacité limitée , Quelle est la valeur minimale du coût maximal dans le bord de coupure? ?

D'abord, il y a une erreur facile à imaginer. , C'est qu'on Trie les bords. , Et je l'ai effacé quand j'étais petit. . Mais parce qu'il y a une limite de longueur totale , Cette suppression peut également supprimer des bords supplémentaires , Comme quand un sous - arbre est brisé , Il y a déjà des bords que j'ai coupés dans ce sous - arbre. , Peut - être pas. \(m\) Limites, Donc ce n'est pas tout à fait vrai. .

Voir max min ,C'est ça? DNA Ça bouge. , Oui, c'est l'idée de la dichotomie. . Le prix à payer pour couper le plus long côté possible , Et nous divisons nos bords en quelque chose qui peut et ne peut pas être coupé . C'est là que nous courons vers le haut. , Disons qu'il y a deux minutes. \(x\)​​​​ Nous avons créé \(f[i]\)​​​ Exprimé par \(i\)​​ Coût minimal de la rupture de toutes les feuilles et racines d'un sous - arbre racinaire ,Donc quand \(k\)​​ - Oui. \(i\)​ Quand le fils de ,Si \(dis[i][k]≤x\)​, C'est - à - dire que ce côté peut être coupé ,\(f[i]+=min(f[k],dis[i][k])\), Sinon, seulement \(f[i]+=f[k]\) La tâche cassée a été confiée à .

Voyons enfin les réponses. \(ans\) Satisfait ou non \(ans≤m\)​ Pour déterminer comment nos deux moitiés se déplacent pour finir la question. .


\[QAQ
\]

Il y a deux autres questions à la fin. :HDU 3586 Et POJ 2152

Voici quelques idées. ,

HDU 3586: Minimiser le maximum (Deux points), Deux points sur la limite supérieure , En forme d'arbre DP Pour juger ;

POJ 2152

Article de référence

【Planification dynamique】ArbreDP Explication complète !Autre article Afghanistan

  1. ArbreDP Introduction détaillée + Titre recommandé

    ArbreDP.Qu'est - ce que c'est?? Pourquoi ce nom? ? Avec les autres DPQuelle est la différence?? Je crois que beaucoup de débutants ont ce problème lorsqu'ils entrent en contact avec une nouvelle idée. . C'est vrai,ArbreDP Pour être précis DPDes idées,Oui.DP Basé sur une structure arborescente . Oui. ...

  2. HypostaseDP Introduction détaillée + Titre recommandé

    Dans la programmation dynamique , Comment s'appelle - t - on habituellement? DP C'est tout. DP,HypostaseDPEt ça ne fait pas exception Ce qu'on appelle la compression d'état , Généralement en utilisant 01 État de la représentation en chaîne , Tirer pleinement parti des caractéristiques des nombres binaires , Simplifier les difficultés de calcul .Par exemple,, Dans le titre où les pièces sont placées sur un échiquier ,Nous pouvons utiliser1Indique quand ...

  3. Planification dynamique——Arbredp

    L'idée de la programmation dynamique comme solution optimale ,Et récursive.Deux points. La cupidité et d'autres pensées fondamentales sont les mêmes. , En fait, il y a beaucoup de théorie des nombres .Théorie des graphes. La structure des données et d'autres algorithmes spécifiques ,Donc cet article, Nous discutons de la combinaison de la structure de l'arbre et de la programmation dynamique dans la théorie des graphes ——Arbredp. ...

  4. poj1417 true liars(Ensemble de recherche + DP)Détails

    Ça fait deux jours. . Tout d'abord, il est clair d'utiliser des ensembles de recherche parallèles pour classifier , Mais la seule façon de déterminer si c'est le cas, c'est la recherche. . Toujours chronométré . Plus tard, lisez le rapport final des autres. , C'est le seul moyen de juger. DP. Objet: C'est tout.p1+p2Particuliers, Diviser en deux groupes ,Groupe Ip ...

  5. UOJ#290. 【ZJOI2017】Cactus Cactus,Tarjan,Nombre,Planification dynamique,Arbredp, Récurrence

    Lien vers le texte originalhttps://www.cnblogs.com/zhouzhendong/p/UOJ290.html Explication du problème C'est une bonne question. ! Tout d'abord,, Si ce n'est pas la sortie directe de cactus 0 . Sinon, Coupez d'abord les bords de l'anneau. . ...

  6. Numérique DP Détails du coffrage

    // pos = Emplacement actuel du traitement ( Généralement de haut en bas ) // pre = Numéro du dernier chiffre ( Le plus haut. ) // status = État à atteindre ,Si oui1 On peut penser qu'on a trouvé la réponse. , Pour revenir. , // Tiens. ...

  7. HDU 1693 Fiche dp Introduction détaillée

    Lien vers le titre    https://vjudge.net/problem/22021/origin Donner unn*mDe01Matrice,1 On y va. 0 Pas de passage , La route à parcourir peut former un anneau et plusieurs anneaux peuvent apparaître , Demande - moi combien c'est différent. ...

  8. Thème de la planification dynamique 01 Solution détaillée au problème du sac à dos HDU 2546 Carte de repas

    J'en prends un exemple. ,Analyse détaillée01 Problème de sac à dos , J'espère que ce sujet sera utile 01 Comprendre le problème du sac à dos aide , Si vous avez des questions sur ce blog, posez - moi des questions. , Progresser ensemble ^_^ Carte de repas Time Limit: 5000/1000 MS (Java ...

  9. Numérique DP Introduction détaillée + Titre recommandé

    \(update:2019-9-6\) Quelque chose dans le blog n'est pas expliqué clairement , Amélioration de l'interprétation correspondante Avant de commencer, Commençons par une question. --Liens vers les sujets Exigences relatives au titre, La différence entre deux bits adjacents est supérieure ou égale à 2, Commençons par construire un essai. . Par exemple,\ ...

  10. LeetCode | DP Détails du sujet

    221 medium     221. Maximal Square Medium Given a 2D binary matrix filled with 0's and 1's, find the ...

Recommandation aléatoire

  1. EclipseIntégration moyenneAntConfiguration (Tourne.)

    En coursEclipse Tout est intégré. ant, Cet article montre comment eclipseUtilisation suivanteant. 1.NouveauJava Project-NouveauJavaDocumentationHelloWorld.java HelloWorld.java pac ...

  2. C++ STL Réalisation:

    C++ STL Réalisation: 1.vector   La structure de données sous - jacente est un tableau , Permet un accès aléatoire rapide 2.list    La structure de données sous - jacente est une liste bidirectionnelle , Prise en charge de l'ajout et de la suppression rapides 3.deque    La structure de données sous - jacente est un contrôleur central et plusieurs tampons ...

  3. dojo.publish Et dojo.subscribe

    Lien vers le texte original:http://www.cnblogs.com/didi/archive/2010/06/13/1757894.html //dojo.publish Et dojo.subscribe  :d ...

  4. U-BOOTProcessus de configuration

    Extrait de:<IntégréLinux Manuel complet de développement des applications > ( Target  :         smdk2410              $1 Architecture:     arm       ...

  5. LintCode-Hash Function

    In data structure Hash, hash function is used to convert a string(or any other type) into an integer ...

  6. Java theory and practice: Thread pools and work queues--reference

    Why thread pools? Many server applications, such as Web servers, database servers, file servers, or ...

  7. Philosophy is systematic reflective thinking on life.

    1. perfect  coding Pensée logique . Pensée abstraite .Pensée divergente knowledge application                     design 2. Java Object: h ...

  8. Jenkins +git +python Effectuer une intégration continue pour les essais d'interface (Essais d'interfacejenkins Intégration continue )

    Utiliserjenkins+git+python Script pour les tests d'interface d'intégration continue ,InjenkinsPlate - forme, Utilisation de plug - ins, etc. , Gérer le Code git Mise à jour du Code de l'entrepôt pour les essais d'interface en cours ,python Effectuer des scripts de test de développement ,git À DISTANCE ...

  9. python Compréhension décorative

    1. Rôle des décorateurs Ajouter une nouvelle fonctionnalité à l'objet décoré sans modifier le code source de l'objet décoré et la façon dont il est appelé Principes: 1. Ne pas modifier le code source de l'objet décoré 2. Ne pas modifier la façon dont les objets décorés sont appelés Objectifs: Ajouter de nouvelles fonctionnalités aux objets décorés 2. Décorateur ...

  10. Tutorial 02_ Familiarisez - vous avec l'utilisation courante HDFSFonctionnement

    ShellRéalisation des commandes: (1)VersHDFS Télécharger n'importe quel fichier texte , Si le fichier spécifié est dans HDFS Existe déjà , Il appartient à l'utilisateur de spécifier s'il faut l'ajouter à la fin du fichier original ou l'écraser. : (2) DeHDFS Télécharger le fichier spécifié dans , Si la langue locale ...