【练习】树形dp

G. Group Homework

time limit per test: 3 s

memory limit per test: 512 MB

input: standard input

output: standard output
No, we don’t want group homework. It’s the place where KaTeX parse error: Expected 'EOF', got '&' at position 7: 1 + 1 &̲lt; 1 can be true. However, you are currently the leader of a group with three members. Luckily, your group members will write everything down for you since you are the prestigious leader. Unluckily, you have to assign the new algorithm homework to your two team members, Mr. Dian and Mr. Beng, who can’t understand the ideas of each other correctly and mess up all the details in the cooperation.

The new homework is about a tree: there are $n$ vertices on the tree with $n-1$ bidirectional edges connecting them. Each vertex $i$ is a problem with a score of $a_i$. You can assign a tree path to each member, then Mr. Dian and Mr. Beng will solve the problems on their path independently. The final score of the homework is decided by the sum of the scores of the vertices visited by exactly one member — as we mentioned before, if both of them solved one problem independently, they will argue a lot about who is right, and all the effort will be in vain.

Now, you — Mr. Ji — want to maximize the final score (as well as the chance not to drop out of school due to too low GPA). Make a wise choice!
Input

The first line of input contains a single integer $n(1\le n\le 2\times 10^5)$, denoting the number of vertices.

The second line contains $n$ integers separated by spaces, the $i$-th integer denotes $a_i(1\le a_i\le 10^4)$.

In the following $n-1$ lines, each contains two integers $u,v(1\le u,v\le n)$, denoting $(u,v)$ is a tree edge.

It is guaranteed that the input edges form a tree of $n$ vertices.

https://www.cnblogs.com/hbhhbh/articles/16858850.html

#include<iostream>
using namespace std;
#include<vector>
#include<map>
#include<algorithm>
const int N=200010;
int n;
vector<int> G[N];
map<int,int> dp1[N];
map<int,int> dp2[N];
int w[N];
//u到子树中最长路径
int dfs1(int u,int fa)
{if(dp1[u][fa])return dp1[u][fa];int xuan=w[u];for(int v:G[u]){if(v==fa)continue;xuan=max(xuan,dfs1(v,u)+w[u]);}return dp1[u][fa]=xuan;
}//dp2 u韦根的子树中，两点间路径，最长
int dfs2(int u,int fa){if(dp2[u][fa])return dp2[u][fa];int xuan=0;int d1=0;int d2=0;for(auto v:G[u]){if(v==fa)continue;//子树中，不经过uxuan=max(xuan,dfs2(v,u));//经过uint t=dfs1(v,u);if(d1<t){d2=d1;d1=t;}else if(d2<t){d2=t;}}
xuan=max(xuan,d1+d2+w[u]);
return dp2[u][fa]=xuan;
}int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);
}int ans=0;
for(int i=1;i<=n;i++){vector<int> l={0,0,0,0};for(auto v:G[i])l.push_back(dfs1(v,i));sort(l.begin(),l.end());reverse(l.begin(),l.end());ans=max(ans,l[0]+l[1]+l[2]+l[3]);
}
for(int i=1;i<=n;i++){for(auto v:G[i]){int t1=dfs2(v,i);int t2=dfs2(i,v);ans=max(ans,t1+t2);}
}
cout<<ans;}

I. Infection

I. Infection

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

A highly propagating bacterium infects a tree of $n$ nodes (with $n-1$ edges, no cycles). These nodes are indexed from $1$ to $n$.

Exactly one node will be infected at the beginning. Each node on the tree has an initial susceptibility weight $a_i$, which represents that node $i$ has a probability of $\frac{a_i}{{\sum }_{i=1}^n{a}_i}$ to become the initial infected node of the tree.

In addition, each node has an infection probability $p_i$, which represents its probability of being infected by adjacent nodes.

Specifically, starting from the initial infected node, if a node is infected, the uninfected node $x$ that is adjacent to it will have a probability of $p_x$ to become a new infected node, and then $x$ can continue to infect its adjacent nodes.

Now, your task is to calculate the probability that exactly $k$ nodes are eventually infected. You need to output an answer for each $k=1,\dots ,n$.

You need to output the answer modulo $10^9+7$, which means if your answer is $\frac{a}{b}$ ($\gcd (a,b)=1$), you need to output $a\cdot b^{-1}\mathrm{mod}10^9+7$, where $b\cdot b^{-1}\equiv 1(\mathrm{mod}10^9+7)$.
Input

The first line contains an integer $n$ ($2\le n\le 2000$), denoting the number of nodes of the tree.

The next $n-1$ lines, each line contains two positive integers $u$ and $v$ ($1\le u,v\le n$), denoting that there is an edge $(u,v)$ on the tree.

Next $n$ lines, the $i$-th line contains three positive integers $a_i,b_i,c_i$, where $a_i$ means as above and $p_i=\frac{b_i}{c_i}$. It is guaranteed that $1\le a_i,b_i,c_i\le 10^9,\sum _{i=1}^n{a}_i\le 10^9,b_i\le c_i,\gcd (b_i,c_i)=1$.
Output

Output $n$ lines, each line contains single integer. The integer on the $i$-th line should be the answer modulo $10^9+7$ when $k=i$.
Example
Input
5
2 1
5 2
3 2
4 3
2 1 5
3 1 2
2 1 1
2 1 1
3 1 2
Output
208333335
166666668
166666668
950000007
508333337
https://blog.csdn.net/yingjiayu12/article/details/129073201

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
const int mod=1e9+7;
ll qpow(ll a,ll b) {ll ans=1;while(b) {if(b&1) ans=(ans*a)%mod;b>>=1;a=(a*a)%mod;}return ans;
}
vector<int>edge[maxn];
int a[maxn],b[maxn],c[maxn];int p[maxn];int ans[maxn];
int n;
int f[2010][2010],g[2010][2010];int Size[maxn];int sum=0;
int Temp1[maxn],Temp2[maxn];
//f不包括初始感染点,g包括初始感染点
void dfs(int u,int pre_u) {Size[u]=1;a[u]=a[u]*sum%mod;f[u][1]=p[u];g[u][1]=a[u];for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==pre_u) continue;dfs(v,u);for(int i=1;i<=Size[u]+Size[v];i++) {Temp1[i]=Temp2[i]=0;}for(int i=1;i<=Size[u];i++) {for(int j=0;j<=Size[v];j++) {Temp1[i+j]=(Temp1[i+j]+f[u][i]*f[v][j]%mod)%mod;Temp2[i+j]=(Temp2[i+j]+g[u][i]*f[v][j]%mod)%mod;if(j) Temp2[i+j]=(Temp2[i+j]+f[u][i]*g[v][j]%mod)%mod;}}Size[u]+=Size[v];for(int i=1;i<=Size[u];i++) {f[u][i]=Temp1[i];g[u][i]=Temp2[i];}}for(int i=1;i<=Size[u];i++) {ans[i]=(ans[i]+(1-p[pre_u]+mod)%mod*g[u][i]%mod)%mod;}f[u][0]=(1-p[u]+mod)%mod;
}
signed main() {n=read();for(int i=1;i<=n-1;i++) {int u=read(),v=read();edge[u].push_back(v);edge[v].push_back(u);}for(int i=1;i<=n;i++) {a[i]=read();b[i]=read();c[i]=read();p[i]=b[i]*qpow(c[i],mod-2)%mod;sum=(sum+a[i])%mod;}sum=qpow(sum,mod-2);dfs(1,0);for(int i=1;i<=n;i++) cout<<ans[i]<<endl;return 0;
}