Բուժաշխատողներ
Միլանդիան երկիր է, որը ունի ծառի տեսք։ Միլանդիայում կան
n քաղաքներ, համարակալված 1,2,...,n թվերով, որոնք միացած են իրար հետ n-1 երկկողմանի ճանապարհներով այնպես, որ կամայական քաղաքից կարելի է հասնել կամայական ուրիշ քաղաք միայն երթևեկելով այդ ճանապարհներով։Միլանդիայի մայրաքաղաքում (որի համարը
1ն է) վերջերս հայտնաբերվել է վտանգավոր սթեմավիրուսը, ինչի պատճառով երկրի նախագահը որոշել է հետագա m օրերի ընթացքում, տեղաբաշխել k բուժաշխատողների բոլոր քաղաքների միջև։ Բուժաշխատողները հնարավոր է ստիպված լինեն որոշ օրեր գնալ ուրիշ քաղաք, օգտագործելով երկրի ճանապարհները։Գիտնականները պարզել են, որ բուժաշխատողը տխրում է, եթե այդ
m օրերի ընթացքում, ինչ որ ճանապարհով անցնելուց մոտիկանում է մայրաքաղաքին (վիրուսի աղբյուրին)։ Քանի որ նախագահը չի ուզում տխուր բուժաշխատողներ իր երկրում, նա ձեզ է հանձնարարում հետագա m օրերի համար տեղաբաշխել բուժաշխատողներին n քաղաքներով այնպես, որ տխուր բուժաշխատողների քանակը լինի հնարավորինս քիչ և iրդ օրը jրդ քաղաքում լինի Ձեզնից պահանջվում է գրել ծրագիր, որը կասի թե որքան է ամենաքիչ հնարավոր տխուր բուժաշխատողների քանակը
m օր հետո։Մուտքային տվյալներ
Մուտքի առաջին տողում տրված է
2 ≤ n,m,k ≤ 1000 բնական թվերը։Հաջորդ n-1 տողերում տրված են 1 ≤ a,b ≤ n (a ≠ b) բնական թվերը, որոնք ցույց են տալիս a և b քաղաքների միջև ճանապարհի գոյություն:Հաջորդ m տողերերից iրդը պարունակում է ci,1, ci,2, ... , ci,n բնական թվերը, որոնց գումարը հավասար է kի:Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ ամենաքիչ հնարավոր տխուր բուժաշխատողների քանակը։
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (7 միավոր)
K = 1
- Ենթախնդիր 2 (18 միավոր)
M = 2
- Ենթախնդիր 3 (10 միավոր)
ci+1,j≤ ci,j1 ≤ i ≤ m-1, 2 ≤ j ≤ nամբողջ թվերի համար,
- Ենթախնդիր 4 (15 միավոր)
K ≤ 10
- Ենթախնդիր 5 (16 միավոր) Ծառը շղթա է,
- Ենթախնդիր 6 (34 միավոր) լրացուցիչ սահմանափակումներ չկան։
Օրինակ
Մուտք | Ելք |
7 3 4
1 2
7 1
3 1
4 3
5 4
6 3
2 0 0 0 0 0 1
0 1 0 1 0 1 1
0 1 0 0 2 0 1 | 1 |
Բացատրություն
Նկարի մեջ կանաչ գույնով պատկերված բուժաշխատողը կլինի տխուր, քանի որ
2րդ օրվանից հետո նա պետք է 6րդ համարով քղաքից գնա 5 Համարով քաղաքը և ընթացքում պետք է անցնի 3 համարի քաղաքով: 6ից 3 տանող ճանապարհը նրան մոտիկացնում է մայրաքաղաքին, և դրա պատճառով նա տխուր է: Օրինակի մնացած բոլոր բուժաշխատողները ուրախ են։
Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB