—¿Por qué empecé con esto antes de terminar la programación de intervalos...
P2664 Juego en Árboles
El problema plantea: tenemos un árbol con n nodos, donde cada nodo tiene un color (c_i). Definimos (s(i,j)) como la cantidad de colores distintos en el camino desde el nodo (i) hasta el nodo (j). Además, $$sum_i=\sum_{j=1}^n s(i, j)$$ Necesitamos calcular todos los (sum_i)
(1 \le n,c_i \le 1e5)
Primero, calcular la cantidad de colores en un camino es complejo, así que consideramos transformar el problema. Esto es similar a un problema anterior de programación de intervalos. Convertimos el conteo de colores en cada camino en cuántos caminos pasan por cada color, lo que simplifica el problema. Ahora solo necesitamos determinar, para cada nodo, cuántos caminos lo atraviesan para poder calcular su contribución. Una solución en (O(n^2)) sería posible realizando un DFS para cada nodo, obteniendo así 40 puntos.
Consideremos la optimización.
La expresión de (sum) es compleja, así que la simplificamos: (sum_i=\sum_{c=1}^{m}(n-t_{i,c})) Donde (m) es el número total de colores, y (t_{i,c}) representa cuántos caminos desde el nodo (i) no pasan por el color (c). Como desde el nodo (i) hay exactamente (n) caminos válidos (incluyendo el camino trivial de un nodo a sí mismo), obtenemos esta expresión. Pero aún es complicada, expandámosla: (sum_i=n*m-\sum_{c=1}^{m}t_{i,c}) Ahora el objetivo es claro, ya que el primer término es constante, solo necesitamos calcular (t).
Observamos que para un color (c_x), si eliminamos todos los nodos de este color y sus aristas adyacentes, el árbol se divide en varios componentes conexos. Dentro de cada componente, no hay nodos de color (c_x), por lo que este color no contribuye en los caminos dentro del componente. Por el contrario, entre diferentes componentes, el color (c_x) siempre contribuye. Sin embargo, esto no es relevante para nuestro problema transformado, donde solo necesitamos identificar los caminos que no contienen un color específico. Para un componente conexo sin el color (c), cada nodo en este componente debería tener (t_{i,c}) incrementado por el tamaño del componente (s), ya que cualquier camino entre dos nodos dentro del componente no contiene el color (c). Esto es similar al caso de los (n) caminos, ya que el camino de un nodo a sí mismo es válido. Sin embargo, este enfoque sigue siendo demasiado lento, ya que necesitaríamos enumerar cada color y luego recorrer todos los nodos, lo que no mejora la complejidad.
Consideremos que el color en sí no es tan importante.¿Cómo interpretar esto? Como enumerar cada color y dividir en componentes conexos es lento, en su lugar enumeramos cada nodo y usamos su color para explorar sus subárboles. Si en un subárbol no encontramos este color, excelente, debemos agregar el tamaño del subárbol a (t). Si encontramos un nodo con el mismo color, no lo contamos. Así podemos recorrer todos los nodos en (O(n)) (cada nodo se procesa exactamente una vez). Para pasar la respuesta, simplemente usamos diferencias. Agregamos al nodo raíz el tamaño de los subárboles que no contienen su color. Luego, al descender en la recursión, transferimos esta contribución a los hijos. Si encontramos un hijo con el mismo color, restamos esta contribución. Así resolvemos el problema.
El proceso de diferenciación sería similar a esto (este diagrama y el código están adaptados de otras fuentes, pero he añadido mis propios comentarios):
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int leer(){
int x;scanf("%d",&x);return x;
}
struct{
int y,sig;
}e[N*2];
int len,Link[N];
void agregar(int x,int y){
e[++len]={y,Link[x]};
Link[x]=len;
}
int f[N],color[N];
int dfn[N],tam[N],tamc[N],tot;
ll tag[N],t[N];
vector<int>o[N];
void dfs(int x,int padre){
tam[x]=1;
dfn[x]=++tot;
for(int i=Link[x];i;i=e[i].sig){
int y=e[i].y;
if(y==padre) continue;
int tmp=tamc[color[x]];
dfs(y,x);
tam[x]+=tam[y];
int s=tam[y]-(tamc[color[x]]-tmp);
tamc[color[x]]+=s;
tag[y]+=s;
while(o[color[x]].size()&&dfn[o[color[x]].back()]>dfn[x]){
tag[o[color[x]].back()]-=s;
o[color[x]].pop_back();
}
}
tamc[color[x]]++;
o[color[x]].push_back(x);
}
void consulta(int x,int padre){
t[x]=t[padre]+tag[x];
for(int i=Link[x];i;i=e[i].sig){
int y=e[i].y;
if(y==padre) continue;
consulta(y,x);
}
}
int main(){
int n=leer(),mx=0;
for(int i=1;i<=n;i++){
color[i]=leer();
mx=max(mx,color[i]);
f[color[i]]=1;
}
for(int i=1;i<n;i++){
int x=leer(),y=leer();
agregar(x,y),agregar(y,x);
}
dfs(1,0);
int m=0;
for(int i=1;i<=mx;i++){
if(!f[i]) continue;
int s=n-tamc[i];m++;
tag[1]+=s;
for(auto x:o[i]) tag[x]-=s;
}
consulta(1,0);
for(int i=1;i<=n;i++) printf("%lld\n",1ll*n*m-t[i]);
return 0;
}
P2081 [NOI2012] Parque de Atracciones Perdido
Primero, este problema tiene detalles extremadamente complejos, y se dice que es de dificultad avanzada.
El problema en realidad consiste en dos partes, cada una con 50 puntos. Primera parte: se nos da un árbol, y necesitamos calcular el costo esperado desde cada nodo hasta todas las hojas, sin pasar por nodos repetidos en ningún camino. La probabilidad de seleccionar cada nodo o de moverse a un nodo adyacente es uniforme. Es decir, si hay (n) nodos, la probabilidad de seleccionar cada nodo es (\frac{1}{n}), y si un nodo tiene (k) aristas, la probabilidad de tomar cada arista es (\frac{1}{k}). Aunque el árbol no tiene una raíz fija, esto no es importante ya que podemos elegir cualquier nodo como raíz. Segunda parte: se añade una arista adicional, creando un ciclo con no más de 20 nodos. También necesitamos calcular el costo esperado para llegar a todas las hojas, pero ahora es válido recorrer todo el ciclo si este es conisderado como una hoja.
Comencemos considerando el árbol, parece evidente que se trata de programación dinámica (DP). Definamos (g[x]) como el costo esperado para bajar desde el nodo actual hasta una hoja, y (f[x]) como el costo esperado para subir desde el nodo actual hasta una hoja. Sin embargo, como la raíz no está fija, "subir hasta una hoja" significa llegar a un padre o ancestro y luego continuar bajando hasta una hoja.
¿Cómo transferimos estos estados? Una vez definidos los estados, la transferencia es bastante clara. Para el array (g), la transferencia es sencilla. Elegimos una raíz arbitraria, recursamos hacia los hijos, al regreso sumamos (g) de los hijos, y finalmente dividimos por el número de hijos después de añadir la distancia al hijo. Específicamente:
void dfs1(int nodo){
g[nodo]=0;
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(vis[y]) continue;
vis[y]=1,padre[y]=nodo,altura[y]=v;
dfs1(y);
g[nodo]+=g[y]+v;
hijos[nodo]++;
}
if(hijos[nodo]) g[nodo]/=hijos[nodo];
}
¿Y qué pasa con (f)? Primero consideremos subir un paso, es decir, llegar al padre. El valor esperado de subir al padre sería el valor esperado de bajar desde el padre menos el valor esperado de bajar desde el nodo actual más la distancia al padre. Esto se debe a que el valor esperado de bajar desde el padre incluye todas las ramas, pero al subir al padre y luego bajar, no podemos volver al nodo actual, por lo que debemos restar la contribución de este nodo. Para ancestros más lejanos, simplemente tomamos el valor del padre del padre, etc. Finalmente, dividimos por el número de aristas del padre (menos 1, ya que no podemos volver al nodo actual) y sumamos la distancia al padre. Si el nodo es el único hijo de su padre, simplemente usamos el valor (f) del padre más la distancia.
void dfs2(int nodo){
if(hijos[padre[nodo]]>1){
f[nodo]=(double)(g[padre[nodo]]*hijos[padre[nodo]]-g[nodo]-altura[nodo]+f[padre[nodo]])/(grado[padre[nodo]]-1)+altura[nodo];
}else f[nodo]=f[padre[nodo]]+altura[nodo];
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(vis[y]) continue;
vis[y]=1;
dfs2(y);
}
}
Finalmente, ¿cómo calculamos el resultado? El costo esperado total es ({\sum_{i=1}^{n}\frac{(longitud_baja + longitud_alta)}{número_de_aristas_salientes}}), y luego dividimos por (n) porque también hay una probabilidad de (\frac{1}{n}) de seleccionar cada nodo. La expresión específica es:
double respuesta=0;
for(int i=1;i<=n;i++) respuesta+=(double)(g[i]*hijos[i]+f[i])/(hijos[i]+(padre[i]!=0));
printf("%.5f",respuesta/n);
La complejidad total es (O(n)) porque cada nodo se procesa exactamente una vez. Ya tenemos 50 puntos.
Ahora consideremos cómo manejar el caso con un ciclo.
Veamos qué dificultades presenta el enfoque del árbol cuando hay un ciclo:
- Si un subárbol contiene un ciclo, es difícil calcular el array (g).
- Si los subárboles de los ancestros contienen un ciclo, también es difícil calcular el array (f).
Estas dificultades surgen porque los ciclos son complejos, especialmente cuando se permite recorrer todo el ciclo si este es considerado como una hoja, lo que hace difícil calcular para cada nodo.
Sin embargo, ¿qué es fácil de calcular? Notamos que es fácil calcular el array (g) para los nodos en el ciclo. Si definimos moverse por el ciclo como "subir" y salir del ciclo como "bajar", entonces el cálculo de (g) es similar al caso del árbol. Dado que el tamaño del ciclo es pequeño (no más de 20 nodos), podemos calcular fácilmente los valores para los nodos fuera del ciclo.
Por lo tanto, designamos todo el ciclo como la raíz.
De esta manera, básicamente es el mismo enfoque que en el árbol. La definición del array (g) para los nodos del ciclo cambia a representar el valor esperado de salir del ciclo, pero esto es solo una forma diferente de decirlo, ya que todo el ciclo es la raíz y no podemos movernos por el ciclo al bajar. Para los nodos fuera del ciclo, la definición de (g) permanece igual.
Para el array (f), solo necesitamos modificar los nodos en el ciclo. Dado que el ciclo es pequeño, podemos recorrer todo el ciclo para preprocesar el valor esperado de salir desde cada nodo del ciclo hacia las hojas. Esto se hace calculando el valor promedio al recorrer el ciclo en ambas direcciones (sentido horario y antihorario). Además, para los nodos directamente conectados al ciclo, necesitamos duplicar el valor (f) del padre porque al subir al ciclo podemos movernos en ambas direcciones. Para los demás nodos, la forma de calcular (f) no cambia. Así resolvemos el array (f), y solo queda calcular el resultado.
El cálculo del resultado es similar: el costo esperado total sigue siendo ({\sum_{i=1}^{n}\frac{(longitud_baja + longitud_alta)}{número_de_aristas_salientes}}). Para los nodos en el ciclo, como hay dos direcciones para moverse (sentido horario y antihorario), necesitamos agregar 1 al denominador. La complejidad es (O(n+k^2)), donde (k \le 20) es el número de nodos en el ciclo, y (k^2) proviene del recorrido en ambas direcciones del ciclo.
Aquí está el código con todos estos detalles, con comentarios detallados que deberían facilitar la comprensión:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int leer(){
int x;scanf("%d",&x);return x;
}
struct{
int y,sig,v;
}e[N*2];
int len,Link[N];
void agregar(int x,int y,int v){
e[++len]={y,Link[x],v};
Link[x]=len;
}
int n,m;
int grado[N],hijos[N],vis[N],padre[N],altura[N],etiqueta[N];
double g[N],f[N];
void dfs1(int nodo){
g[nodo]=0;
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(vis[y]) continue;
vis[y]=1,padre[y]=nodo,altura[y]=v;
dfs1(y);
g[nodo]+=g[y]+v;
hijos[nodo]++;
}
if(hijos[nodo]) g[nodo]/=hijos[nodo];
}
void dfs2(int nodo){
if(hijos[padre[nodo]]>1){
if(!etiqueta[nodo]) f[nodo]=(double)(g[padre[nodo]]*hijos[padre[nodo]]-g[nodo]-altura[nodo]+f[padre[nodo]])/(grado[padre[nodo]]-1)+altura[nodo];
else f[nodo]=(double)(g[padre[nodo]]*hijos[padre[nodo]]-g[nodo]-altura[nodo]+f[padre[nodo]]*2)/(grado[padre[nodo]]-1)+altura[nodo];
}else f[nodo]=f[padre[nodo]]+altura[nodo];
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(vis[y]) continue;
vis[y]=1;
dfs2(y);
}
}
int inicio,fin,sig[N],alturaN[N];
vector<int>o;
void dfs3(int nodo,int ant){
vis[nodo]=1;
if(inicio) return ;
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(y==ant) continue;
if(vis[y]){
if(inicio) return ;
inicio=nodo,fin=y;
padre[y]=nodo;
sig[nodo]=y;
altura[y]=alturaN[nodo]=v;
return ;
}
if(inicio) return ;
padre[y]=nodo;
sig[nodo]=y;
altura[y]=alturaN[nodo]=v;
dfs3(y,nodo);
if(inicio) return ;
}
}
void inicializar(){
memset(vis,0,sizeof vis);
for(auto nodo:o) vis[nodo]=1;
}
int main(){
n=leer(),m=leer();
for(int i=1;i<=m;i++){
int x=leer(),y=leer(),w=leer();
agregar(x,y,w),agregar(y,x,w);
grado[x]++,grado[y]++;
}
if(m==n-1){
vis[1]=1,dfs1(1);
memset(vis,0,sizeof vis);
vis[1]=1,dfs2(1);
double respuesta=0;
for(int i=1;i<=n;i++) respuesta+=(double)(g[i]*hijos[i]+f[i])/(hijos[i]+(padre[i]!=0));
printf("%.5f",respuesta/n);
return 0;
}
dfs3(1,0);
for(int i=inicio;i!=fin;i=padre[i]) o.push_back(i),vis[i]=1;
o.push_back(fin),vis[fin]=1;
inicializar();
int sz=o.size();
for(auto nodo:o) dfs1(nodo);
for(auto nodo:o){
double ahora=1;
f[nodo]=0;
for(int j=sig[nodo];j!=nodo;j=sig[j]){
if(sig[j]!=nodo) f[nodo]+=ahora*(altura[j]+g[j]*hijos[j]/(hijos[j]+1));
else f[nodo]+=ahora*(altura[j]+g[j]);
ahora=ahora/(hijos[j]+1);
}
ahora=1;
for(int j=padre[nodo];j!=nodo;j=padre[j]){
if(padre[j]!=nodo) f[nodo]+=ahora*(alturaN[j]+g[j]*hijos[j]/(hijos[j]+1));
else f[nodo]+=ahora*(alturaN[j]+g[j]);
ahora=ahora/(hijos[j]+1);
}
f[nodo]/=2;
}
inicializar();
for(auto nodo:o){
for(int i=Link[nodo];i;i=e[i].sig){
int y=e[i].y,v=e[i].v;
if(!vis[y]) vis[y]=etiqueta[y]=1,dfs2(y);
}
}
inicializar();
double respuesta=0;
for(int i=1;i<=n;i++){
if(!vis[i]) respuesta+=(double)(g[i]*hijos[i]+f[i])/(hijos[i]+1);
else respuesta+=(double)(g[i]*hijos[i]+f[i]*2)/(hijos[i]+2);
}
printf("%.5f",respuesta/n);
return 0;
}